# 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$)...
3k views

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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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: ...
11k views

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 ...
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$ ...
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 ...
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 ...
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 ...
113 views

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 ... 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? 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 ... 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 ... 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 \... 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 ... 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 ... 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 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: ... 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. 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}\... 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{...
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 ...