Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
55
votes
3answers
34k 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$)...
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
59 views

Boolean variable that captures whether an inequality holds

I have an integer linear program with variables $x_1,\dots,x_n$. I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold. I want to introduce a boolean ...
3
votes
1answer
1k views

Express a “complex” IF-Statement to Linear Programming

In our current project we need to model the following if-statement in linear programming: If T1 < b < T2 then z = s else z = 0 where T1 and T2 are two ...
3
votes
1answer
1k views

Converting If-else condition to Linear Programming

I have a constraint in a linear programming formulation with two variables: $X \ge Y$ To which I want to apply the following if-else conditions: ...
3
votes
3answers
4k views

“Greater than” condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
6
votes
2answers
900 views

A variant of the Assignment Problem

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
23
votes
1answer
3k views

Sorting as a linear program

A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, ...
4
votes
2answers
308 views

Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
11
votes
1answer
1k views

Does linear programming admit a strongly polynomial-time algorithm?

The linear programming problem: find a strongly-polynomial time algorithm which for given matrix A ∈ Rm×n and b ∈ Rm decides whether there exists x ∈ Rn with Ax ≥ b. I know that Steve Smale's lists ...
7
votes
3answers
1k views

Finding all solutions to an integer linear programming (ILP) problem

My problem is to find all integer solutions to an ILP. As an example, I'm using an ILP with two variables, but I may have more than two variables. I describe the method I currently use to solve this ...
3
votes
1answer
762 views

How to solve an ILP problem with conditions in an objective function?

I have came accross this link. I have an integer linear programming (ILP) problem $$\max_{(x_1, x_2,\ldots, x_n)}\sum_{i=1}^n x_i\cdot f(x_i),$$ $$\text{subject to } \begin{cases} ..., &(1)\\ L≤...
1
vote
0answers
18 views

Given a set of solutions, find an IP formulation with the same solution set

Input: A list of integer variables $x_1, ..., x_n$. A finite set of feasible solutions $S \subset \mathbb{Z}^n$. Task: Find an integer linear program (IP) on the integer variables $x_1,...,x_n$ ...
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 \...
6
votes
2answers
7k 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
1answer
206 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 ...
4
votes
1answer
423 views

Minimum spanning tree formulation as integer program

The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a ...
3
votes
2answers
288 views

How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
3
votes
0answers
57 views

Computing the line equations of two crossing tangents in a point set separated by a vertical line?

I have provided a picture as an example. We have two point sets, P and Q. P is to the left of this vertical line (named x = x0), and Q is to the right of it. The goal is to compute the line equations ...
2
votes
3answers
124 views

Need Help Understanding MST Cutset Formulation

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: ...
1
vote
1answer
334 views

Linear programming, Checking a constraint based on condition

I have a constraint $X \ge Y$ in a Linear programming formulation, where both $X$ and $Y$ are binary. I want to check this constraint on a condition like: ...
1
vote
1answer
2k views

Converting if-then-else condition to integer linear programming with equality constraints

I have an if-then-else condition with three binary variables $A$, $B$ and $C$: if A = 1 then B = 1 else B = C How do I express this as an ...
1
vote
0answers
47 views

Computing line equations of two crossing tangents [duplicate]

Pictured is the problem in question. How do I compute the line equations for these two crossing tangents? These lines happen to be supporting two point sets for two convex hulls.
1
vote
0answers
83 views

“Greater than 0” condition in integer linear program with a binary variable [duplicate]

How can one model the following condition in an integer linear program? $$ y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases} $$ Where $y \in \{0,1\}$ and $x \in \...
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
50 views

Minimal paths as solution of a linear program of a special network flow

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...