Questions tagged [linear-programming]
Optimization with a linear objective function, subject to linear equality and linear inequality constraints.
34
questions
73
votes
3
answers
49k
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$)...
D.W.♦
- 143k
14
votes
3
answers
3k
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,...
D.W.♦
- 143k
3
votes
1
answer
352
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 ...
D.W.♦
- 143k
8
votes
3
answers
3k
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 ...
- 81
4
votes
5
answers
8k
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 \...
- 91
3
votes
1
answer
4k
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 ...
- 33
3
votes
1
answer
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:
...
- 229
6
votes
2
answers
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 ...
- 241
2
votes
1
answer
5k
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 ...
- 229
0
votes
1
answer
27
views
MAX-LP: maximize number of linear inequalities satisfied
Consider the following variant of linear programming, where we want to maximize the number of linear inequalities that are satisfied:
Input: linear inequalities $A_1x\le b_1$, ..., $A_nx \le b_n$; an ...
D.W.♦
- 143k
4
votes
2
answers
534
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 ...
- 160
12
votes
1
answer
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 ...
- 234
9
votes
3
answers
13k
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:
...
- 301
7
votes
1
answer
11k
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
\...
- 353
3
votes
1
answer
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≤...
- 165
3
votes
3
answers
452
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 ...
- 163
1
vote
0
answers
29
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$ ...
- 11
7
votes
1
answer
485
views
Given 2 sets of n points: minimize sum of traveled distances
I am given two sets $S, T$ each of $n$ points in $\mathbb{R}^k$, I want to find a bijection $a : S \rightarrow T$, such that $$\sum_{s \in S} d(s, a(s))$$ gets minimized, with $d$ being the Euclidean ...
- 773
5
votes
2
answers
613
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 ...
- 223
5
votes
1
answer
292
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,023
4
votes
2
answers
113
views
On the hardness of satisfying K number of linear constraints
Background: Normally in linear programing we have some objective function
$$\text{maximize}\sum_{i = 1}^n a_i x_i $$
$$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq ...
- 153
3
votes
2
answers
643
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?
- 163
3
votes
0
answers
84
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 ...
- 73
2
votes
1
answer
157
views
Approximate LP for vertex cover problem
I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
- 131
2
votes
0
answers
1k
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 \...
- 21
1
vote
0
answers
169
views
Fixed Parameter Tractable for Special Vertex Cover using ILP
The problem I'm trying to solve reads as follows:
Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
- 317
1
vote
1
answer
71
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 ...
- 683
1
vote
1
answer
84
views
Formulate a 2-clustering problem in LP
The problem:
Suppose there are $n$ points in plane, and we want to partition points into two clusters such that sum of diameter of clusters is minimized. The diameter of cluster is maximum distance ...
- 1
1
vote
1
answer
715
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:
...
- 229
1
vote
0
answers
63
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.
- 73
1
vote
0
answers
1k
views
Restriction for greater than constraint in linear programming
I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply:
\begin{equation}
x=
\begin{cases}
0, & \text{if}\...
- 11
0
votes
1
answer
319
views
"Greater than AND smaller than" condition in integer linear program with a binary variable
I found this related question, but that's not quite it
Is it possible to model this with integer programming:
$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
- 1
0
votes
1
answer
188
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 ...
- 649
0
votes
1
answer
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 ...
- 1