Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
26
questions
66
votes
3answers
42k 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$)...
13
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,...
3
votes
1answer
226 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 ...
4
votes
3answers
6k 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 \...
8
votes
3answers
2k 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
2k 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
2k 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:
...
6
votes
2answers
1k 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 ...
4
votes
2answers
460 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 ...
12
votes
1answer
2k 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 ...
8
votes
3answers
11k 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:
...
3
votes
1answer
1k 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
26 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$ ...
7
votes
1answer
9k 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
\...
5
votes
1answer
247 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
492 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
0answers
68 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 ...
3
votes
3answers
292 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:
An ...
3
votes
2answers
435 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?
2
votes
1answer
4k 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
634 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 \...
1
vote
0answers
53 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
1answer
43 views
Check if a row is in the span of a matrix
Suppose I have a matrix $M$ over $GF(2)$ with rows that represent a system of linear equations:
A xor B xor C = 1
A xor B xor D = 1
X xor A xor Z = 0
etc...
For a new external row, I want the ...
1
vote
1answer
649 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:
...
0
votes
1answer
2k 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
106 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 ...
