Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

Filter by
Sorted by
Tagged with
4
votes
1answer
75 views

Unfeasible linear program becomes feasible if a variable is removed

Apologies, not a computer scientist by trade but I'm playing with linear programming these days. Let $\{x_i\}$ be $N$ optimization variables with bounds $$l_i \leq x_i \leq u_i$$ I'm interested in ...
0
votes
1answer
42 views

Branch and bound stanford slides doubt

On the 6th slide at https://web.stanford.edu/class/ee364b/lectures/bb_slides.pdf, while defining L2 and U2, why are we taking min for both?
1
vote
1answer
292 views

Restrictions that set binary variable to 1 when integer variable equals x, 0 otherwise

I have this problem: I'm building an integer linear program, which I'm going to give to an ILP solver. I have a binary variable Y which can be either 1 or 0 and an integer variable MONTH which takes ...
2
votes
0answers
96 views

Facility location on a Sphere with great circle distance

I am looking for an algorithm to find the point that minimizes the sum of the great circle distances to a set of fixed points on a sphere. In more detail: Given $x_1,\ldots, x_k$ fixed points in the ...
0
votes
1answer
444 views

Please explain linear programming as seen for this load balancing problem

I have at hand a linear program related to load balancing. However I have no idea what this is and wikipedia gives me something too simplified/abstract to be useful. I wonder if someone can explain ...
1
vote
0answers
122 views

Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem

I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
6
votes
3answers
8k views

Linear programming with absolute values

I know that sometimes we can use absolute values into the objective functions or constraints. Is it always possible to use them, anywhere ? Example of use of absolute values: ...
5
votes
0answers
68 views

Uniform Sampling on Intersection of Faces of Simplices [closed]

I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints $$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
2
votes
1answer
273 views

Inventory Routing - Subtour Elimination [closed]

I'm trying to implement a Inventory Routing Problem with Branch-and-Cut. But I'm facing with an issue regarding subtour elimination. (http://www.danflash.com/files/irp.pdf) The paper describes the ...
2
votes
1answer
474 views

Time complexity of linear program? [closed]

I have built a heuristic algorithm for approximately solving an NP complete graph problem by recursive linear relaxations. In each recursion, the algorithm returns a reduced graph, with number of ...
3
votes
1answer
141 views

A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
5
votes
0answers
43 views

Authors of Complementary Slackness

Who were the first researchers to prove the Complementary Slackness condition for linear programming? I believe that strong optimality was proved by Gale, Kuhn, and Tucker in 1951, but I couldn't ...
0
votes
1answer
1k views

Express XOR with multiple inputs in zero-one integer linear programming (ILP)

In the below post, it is explained how to express xor of two variables as linear inequalities. Express boolean logic operations in zero-one integer linear programming (ILP) Naturally, the xor of ...
0
votes
1answer
489 views

Can you generate random linear programming problems?

I looked at Linear Programming, and it are problems like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. Cabinet ...
2
votes
1answer
72 views

Does there exist a problem that is hard to do in parallel? [closed]

I am looking for a workload which is hard to paralellise/distribute between multiple machines. For example, integer factorization does not go 10 times faster if you have 10 machines to split the ...
3
votes
0answers
29 views

What is the most efficient algorithm for finding the bounding inequalities of a cone given the extremal rays?

Say that I am given a cone, as specified by the extremal rays whose facets form its convex hull, what is the most efficient algorithm that finds the linear-rank inequalities whose intersection defines ...
2
votes
0answers
130 views

Practical implications of strongly polynomial time algorithm for linear programming

Why do people care about whether a strongly polynomial time algorithm for linear programming exists or not? Does this have any practical improvement?
0
votes
1answer
83 views

Basic linear programming question

Trying to answer this question: A factory produces chocolate and candy. In order to produce 100 kilograms of chocolate, the factory has to use machine A for 1 hour, machine B for 4 hours, and machine ...
2
votes
1answer
186 views

Scheduling Problem Optimisation using LP solvers

I am currently working on a scheduling system which schedules individuals based on timeslots that have the following attributes: (1) Day of Week (2) Month (3) Session(AM/PM). The individuals ...
6
votes
0answers
266 views

How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
1
vote
1answer
854 views

ILP and number of variables in constraints

This question is about the time impact of the length (i.e. number of variables) of the constraints in an Integer Linear Programming formulation. Most people try to reach the minimum number of ...
3
votes
1answer
483 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} \...
3
votes
1answer
126 views

Given an optimal solution to the LP, show how it can be used to construct a directed cycle with minimal directed cycle mean cost

Let $\mathcal G = (\mathcal V, \mathcal A)$ be directed graph with associated edge costs $c_{i,j}$ that has at least one directed cycle. Define the directed cycle mean cost to be $\frac {\{\text {sum ...
2
votes
1answer
188 views

Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)

Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: Driving the artificial variables out of the basis. The description is as ...
2
votes
1answer
186 views

How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value?

The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity. It is possible that the max-flow and min-cut is equal to $\infty$. However, reading ...
3
votes
1answer
649 views

Dual problem of a maximization primal problem $P$?

Suppose we have a primal problem $P$ which is stated as a maximization problem $\max c^{T} x$. The dual problem is defined (Introduction to Linear Optimization by Dimitris Bertsimas) only for a ...
2
votes
1answer
129 views

Assuming finite optimal cost of a specific LP, find an optimal solution directly

Minimize $\sum^n_{i=1} c_i x_i$ subject to $\sum^n_{i=1} a_i x_i = b$ (a single constraint), $x_i \ge 0$. Derive a simple test for feasibility of this problem Assuming the optimal cost is ...
6
votes
1answer
207 views

Finding a perfect matching using an LP

I have a basic question about the power of Linear Programming that has been bothering me for some time. I believe there is something simple I am missing. Linear Programming is $\mathsf{P}$-complete, ...
1
vote
1answer
246 views

Feasible solution existence

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty. Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is ...
5
votes
2answers
1k views

Proof of Strong Duality Via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
0
votes
1answer
142 views

Check constraint under some condition in linear programming

I would like to minimize linear pseudo-boolean function $$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$ subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where $c_1,\dots c_5, \...
2
votes
1answer
2k views

Advantage of MTZ problem formulation of TSP

In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance. I understand how MTZ ...
1
vote
0answers
103 views

What is linear relaxation in the context of bayesian networks? [closed]

To add onto the question, how are elliptical differential equations applicable in this context? I was listening to a talk about Bayesian networks and someone asked if they were using differential ...
3
votes
1answer
555 views

Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
1
vote
2answers
516 views

Applications for boolean logic operations in zero-one integer linear programming (ILP) [closed]

It is nice to know that every boolean formula can be expressed by zero-one integer programming by this answered question. But are there any applications? To be more precise: Are there papers which ...
2
votes
1answer
308 views

What's the dual problem of stable matching?

So the dual problem of max-flow is min-cut. What's the dual problem of stable matching?
2
votes
1answer
2k views

Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables. If we set the $c^T$ vector of the objective $\text {...
5
votes
2answers
278 views

Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). ...
10
votes
1answer
4k views

Short and slick proof of the strong duality theorem for linear programming

Consider the linear programs \begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & \...
5
votes
0answers
39 views

Does it make sense to examine the dual of a feasbility problem?

Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
-1
votes
1answer
2k views

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n

How to minimize the sum of difference of element in sub-sequence of array of length k from given sequence of length n ? for example : for n=10 1 2 3 4 10 20 30 40 100 200 the sub-sequence of length ...
1
vote
1answer
683 views

Linear Programming: algorithm to check if ratios can be combined with n bottles to equal a given ratio

Say you have n bottles. each with a ratio of $(a_i: b_i: c_i)$. ($a_i/(a_i+b_i+c_i),\cdots$ swap out the numerator for $b_i$ and $c_i$ respectively). Now you are given a ratio of $(a:b:c)$. Use ...
1
vote
2answers
1k views

Filling Rows of a Matrix Subject to Conditions

I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that: ...
6
votes
1answer
7k views

Checking Feasibility of Linear Program in Polynomial Time

Given a linear system of the form: $$\begin{array}{c} x_r = a \quad x_j = b \\ c_1x_1 + c_2x_2 + \ldots + c_nx_n = N \\ x_1+x_2 + x_3 + \ldots + x_n = k\\ 0 \le a,b,x_1,x_2,x_3...x_n \le 1\\ k \ge 0 \...
1
vote
1answer
545 views

Nash Equilibrium of 2-players game

I have a rather interesting exercise in Game Theory. Assume there is a 2-players game, and player $i$ has $n_i$ pure strategies. The game is given by listing the payoffs for each player for each $n_1 ...
5
votes
1answer
207 views

Use complementary slackness to prove the LP formulation of max-flow only need polynomial number of path constraints

This is a homework problem for a class that ended 2 years ago, I'm learning it by myself. Consider a directed graph $D=(V,A)$, $s,t\in V$. $A=\{a_1,\ldots,a_n\}$. Let $P=\{p_1,\ldots,p_m\}$ be the ...
3
votes
0answers
94 views

Start simplex method from feasible internal point

I have one algorithm that generates a feasible solution to a linear programming problem. However, it is very likely that this is not a corner point. This makes it not suitable for direct use as an ...
0
votes
1answer
1k views

Algorithm to solve job assignment problem

Can someone suggest an algorithm to solve job assignment problem with condition? With condition means that some jobs cannot be done by some workers. For example table as shown below: In this table x ...
57
votes
3answers
35k views

Express boolean logic operations in zero-one integer linear programming (ILP)

I have an integer linear program (ILP) with some variables $x_i$ that are intended to represent boolean values. The $x_i$'s are constrained to be integers and to hold either 0 or 1 ($0 \le x_i \le 1$)...
2
votes
0answers
82 views

Issues with an optimization problem

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...