# Questions tagged [linear-programming]

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

34 questions
Filter by
Sorted by
Tagged with
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$)...
• 143k
3k views

• 91
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
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
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 ...
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
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 ...
• 143k
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
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
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
11k views

• 165
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
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
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
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
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
113 views

• 1
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
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 ...