37
votes
Accepted
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
If $x$ is binary: Then the "if" condition really means either "$x = 0$" or "$x=1$".
To enforce "if $x=0$ then $y=1$": use
$$y \ge 1-x.$$
To enforce "if $x=1$ then $y=1$": use
$$y \ge x.$$
If you ...
- 13.2k
25
votes
Accepted
What is the "big-M" method? And are there two of them?
People do use the term "big-$M$ method" to mean two different things. In both cases, the name refers to the use of a large constant, often denoted $M$.
The first use of the term refers to a method ...
- 13.2k
19
votes
Accepted
What is the difference between integer programming and constraint programming?
You have asked a broad question, so I will provide a broad answer.
Integer programming typically refers to integer linear programming which is a mathematical modeling and solution paradigm. Decisions ...
- 1,542
18
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Here is a nice, succinct, and easy to understand reference for how to do all this and more. Answers to many future questions can be handled by referencing the appropriate section number in this ...
- 13.8k
15
votes
Accepted
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
Let $M$ be a new parameter (constant) that equals a large number.
Greater-than-or-equal-to constraints:
The constraint is $a_1x_1 + \cdots + a_nx_n \ge b$. Rewrite it as
$$a_1x_1 + \cdots + a_nx_n \...
- 13.2k
15
votes
Accepted
Does it make sense to use strict equality constraints in optimization?
I suspect you read that actual floating point optimization solvers treat strict inequalities ($<$ and $>$) as non-strict inequalities ($\le$ and $\ge$). Solvers also give themselves a fudge ...
- 13.8k
14
votes
How to linearize min function as a constraint?
Here is an answer that uses the same approach as in this answer, but converted from $\max\{\cdot,\cdot\}$ to $\min\{\cdot,\cdot\}$. I'll write the constraint in a more general form:
$$X = \min\{x_1,...
- 13.2k
13
votes
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
These are know as "indicator constraints" or "on/off" constraints. The best formulation is the convex-hull one, it includes the optimal big-M value plus additional non-redundant constraints, here's a ...
- 300
13
votes
Accepted
Rewriting if-then constraints of binary summations
In conjunctive normal form, you want to enforce:
\begin{align}
&\quad \quad \quad\bigvee_b x_{i,j}^{a,b} \implies \bigwedge_{u,v}\neg y_{u,v}^{a} \quad&\forall a,i,j\\
&\equiv \quad\neg \...
- 13.7k
12
votes
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Rather than linearising the logical constraint, I would try the logical constraints built in a solver. Gurobi and SCIP both have indicator constraints.
My colleague works with these a lot and he’s ...
- 1,245
12
votes
Accepted
Expressing a chain of boolean ORs using ILP involving different variables
Let $P$ be the set of $(i,j)$ pairs. Here’s a derivation via conjunctive normal form:
\begin{equation}
\bigvee_{(i,j)\in P} \left(x_i \implies x_j\right) \\
\bigvee_{(i,j)\in P} \left(\neg x_i \vee ...
- 33.6k
12
votes
Accepted
Linearize x different of y in ILP
I recommend a third approach, similar to yours but linear:
\begin{align}
x + 1 - y &\le M_1 z \tag1 \\
y + 1 - x &\le M_2 (1-z) \tag2 \\
\end{align}
Constraint $(1)$ enforces $z=0 \implies x + ...
- 33.6k
11
votes
Accepted
MIP: If integer variable $>0$ it should be equal to other integer variables $>0$
Let $b_n$ be a binary indicator variable, and let integer variable $y$ be the common value of the positive $x_n$. Then you want to enforce $x_n=b_n y$, which you can linearize using the formulation ...
- 33.6k
11
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
I recommend Formulating Integer Linear Programs: A Rogues' Gallery:
The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full ...
- 1,895
11
votes
Constraint for two binary vectors to be different
Let binary decision variable $x_{ijk}$ indicate whether columns $j$ and $k$ (with $j<k$) differ in row $i$, and impose linear constraints
\begin{align}
\sum_i x_{ijk} &\ge 1 &&\text{for ...
- 33.6k
11
votes
Accepted
How to transform a logical constraint with integer variables?
You can derive the desired linear constraint by rewriting in conjunctive normal form and rearranging to an equivalent implication:
$$
(x_1 \land (y\ge 2)) \implies x_2 \\
\lnot (x_1 \land (y\ge 2)) \...
- 33.6k
10
votes
Accepted
ILP Constraint to ensure exactly one constraint from a set of constraints is satisfied
You can add an extra binary that equals $1$ if and only if the first constraint is satisfied:
\begin{align}
x_1+x_2+x_3 &\ge \delta\\
x_1+x_2+x_3 &\le 3\delta\\
x_4+x_5+x_6 &\ge 1 - \delta\...
- 13.7k
10
votes
Accepted
Complicated constraint with logical operators in PuLP
Suppose your two arrays are indexed by $I$ and $J$, and let $x_i$ be the binary variable.
zero or one elements may be selected from first array:
$$\sum_{i\in I} x_i \le 1 \tag1$$
zero, one, or many ...
- 33.6k
10
votes
MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$
Assuming $x_i$ variables are binary, the contraposition reads as follows:
$$
\delta = 0 \implies \left( \sum_{i=1}^n x_i \le 1 \right)\vee \left( \sum_{i=1}^n x_i \ge 3 \right)
$$
Define a binary ...
- 13.7k
10
votes
Binary logical constraint dependent on indices
You could convert to CNF.
$$(a = b) \implies (c = d)$$ can be expressed by:
$$0 \le a + b + c - d \le 2$$
$$0 \le a + b + d - c \le 2$$
- 242
9
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015?
- 191
9
votes
How to formulate: each pair of elements in $A$ has one common unit in $B$
If you don’t require linear constraints, you can introduce (or reuse) binary variables $y_{a.b}$ and quadratic constraints
$$\sum_{b\in B} y_{a_1,b} y_{a_2,b} \ge 1 \qquad \forall a_1,a_2\in A,$$
for ...
- 33.6k
9
votes
If-then constraints in MIP programming
Let's just consider one constraint, since they all have the same form:
if x >= 0 and x < 1 then y <= 10 and
First, you really can't test for $x<1$, ...
- 13.2k
9
votes
Accepted
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
For boolean formulas, you can use the following systematic approach. First, convert your formula to conjunctive normal form. Wikipedia details how to do this.
Applied to this specific case it follows ...
- 6,362
9
votes
Accepted
Model "If, then" constraint
You want to enforce
$$\left(\bigwedge_{i \in I} \lnot x_i\right) \implies \sum_{j \in J} x_j = n.$$
Introduce a new binary variable $y$ and enforce
$$\left(\bigwedge_{i \in I} \lnot x_i\right) \...
- 33.6k
9
votes
Accepted
How to transform this logical if-then constraint?
Indeed, for the first constraint you can use:
$$
x+y+z \le 2
$$
For the second one, it might be easier to model the contraposition:
$$
z=0 \quad \Rightarrow \quad x+y \ge 2 \quad \Rightarrow \quad x=y=...
- 13.7k
9
votes
Accepted
Binary logical constraint dependent on indices
You can enforce $X_t=X_{t-1}\implies Y_{it}=Y_{it-1}$ with additional binary variables $\omega_{0t},\omega_{1t},\omega_{2t}$ as follows:
\begin{align}
X_t+X_{t-1}&=0\omega_{0t}+1\omega_{1t}+2\...
- 13.7k
8
votes
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
If I understand your question correctly then you want to model that if $$a_1+a_2+a_3\geq 1$$ then it follows that $$b_1+b_2+b_3\geq 1.$$ Since $A \implies B$ is equivalent to $\neg A \lor B$ we want ...
- 2,033
8
votes
Binary variable to count appearances
As LarrySnyder610 said, you cannot do exactly what you want when $x_i$ is continuous. (You can if it is an integer variable.) I discussed how to model this particular issue here: Flagging a Specific ...
- 40.1k
8
votes
Difference between Chance constraints and logical constraints
These two types of constraint are totally different in terms of their applications in modeling. In fact, the way of using these constraint types (based on your modeling approach) end up in two totally ...
- 8,677
Only top scored, non community-wiki answers of a minimum length are eligible