Linked Questions

2 votes
0 answers
2k 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 \...
Swaz's user avatar
  • 21
40 votes
4 answers
24k views

Why is linear programming in P but integer programming NP-hard?

Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear ...
Sasha the Noob's user avatar
15 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.'s user avatar
  • 158k
4 votes
5 answers
10k 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 \...
Salah's user avatar
  • 91
14 votes
2 answers
671 views

Does every NP problem have a poly-sized ILP formulation?

Since Integer Linear Programming is NP-complete, there is a Karp reduction from any problem in NP to it. I thought this implied that there is always a polynomial-sized ILP formulation for any problem ...
andy's user avatar
  • 253
3 votes
1 answer
4k views

Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?

Karp's 21 NP-complete problems show that 0-1 integer linear programming is NP-hard. That is, an integer linear program with binary variables. If we set the $c^T$ vector of the objective $\text {...
Mat's user avatar
  • 502
1 vote
1 answer
5k views

Expressing conditional in linear program [duplicate]

I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are: if B > 0 A = 1 else A = 0 ...
asm_nerd1's user avatar
  • 229
2 votes
1 answer
4k views

Use max operation in a constraint in Linear Programming

I have liner programme with set of $x_{3n}$ variables where $x_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve. Using these variables, I want to form following constraint : $max(...
Abhay's user avatar
  • 123
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: ...
asm_nerd1's user avatar
  • 229
5 votes
2 answers
819 views

How to reduce the low-rank matrix completion problem to integer programming?

Consider the low-rank matrix completion problem: Given an integer $k$ and a subset of entries of some $n \times n$ matrix, fill in the rest of the entries so that the resulting matrix has rank at ...
Csabo E.'s user avatar
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 ...
piwa's user avatar
  • 33
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 ...
Ahmed's user avatar
  • 1
5 votes
2 answers
338 views

Find a binary matrix so that no vector from {-1,0,1}^n is in its kernel

Given integers $n,m$, I want to find a $m \times n$ binary matrix $X$ such that there does not exist any non-zero vector $y \in \{-1,0,1\}^n$ with $Xy=0$ (all operations performed over $\mathbb{Z}$). ...
marshall's user avatar
  • 143
4 votes
2 answers
848 views

Schedule tasks from a weighted list with time frame constraints

I'm attempting to create an automatic scheduler from a list of tasks I have available. Here are the key points: Each task has been given a priority beforehand and the algorithm should try to maximize ...
Lindenk's user avatar
  • 143
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≤...
Nick's user avatar
  • 175

15 30 50 per page
1
2 3 4 5