The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
7
votes
0answers
247 views

Can the solution to a POMDP be found using linear programming?

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is: $$min_{V(x)} \sum_x \alpha(x)V(x)\\...
10
votes
3answers
2k views

Cast to boolean, for integer linear programming

I want to express the following constraint, in an integer linear program: $$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$ I already have the integer variables $x,...
2
votes
1answer
169 views

Modeling $(x > 0 \wedge y > 0) \Leftrightarrow z > 0$ in a linear program: impossible?

In this question, we see how to model boolean logic in $0 - 1$ ILPs. Moving to a relaxation, modelling $(x > 0 \vee y > 0) \Leftrightarrow z > 0$ with $x,y,z \in [0,1]$ with linear ...
3
votes
1answer
87 views

Are some Integer programming formulations completely useless for relaxation?

I was tasked with constructing an integer programming formulation for an NP-hard problem, and then with specifying its LP relaxation and the resulting approximation factor. The problem is that, while ...
4
votes
3answers
198 views

Help wrapping my head around a combinatorial optimization problem

Here's the problem I'm trying to solve: I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight ...
4
votes
1answer
78 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
295 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
99 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
445 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
123 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
487 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
143 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
498 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
131 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
271 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
863 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
489 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
190 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
199 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
692 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
134 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
215 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
251 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
105 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
594 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
523 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
311 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
686 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
550 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 ...