Skip to main content
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 ...
LarrySnyder610's user avatar
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 ...
LarrySnyder610's user avatar
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 ...
alerera's user avatar
  • 1,542
17 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 ...
Mark L. Stone's user avatar
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 \...
LarrySnyder610's user avatar
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,...
LarrySnyder610's user avatar
14 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 ...
Mark L. Stone's user avatar
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 ...
Hassan's user avatar
  • 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 \...
Kuifje's user avatar
  • 13.5k
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 ...
Edward Lam's user avatar
  • 1,235
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 + ...
RobPratt's user avatar
  • 32.3k
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
SecretAgentMan's user avatar
11 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 ...
RobPratt's user avatar
  • 32.3k
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 ...
RobPratt's user avatar
  • 32.3k
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)) \...
RobPratt's user avatar
  • 32.3k
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\...
Kuifje's user avatar
  • 13.5k
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 ...
RobPratt's user avatar
  • 32.3k
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 ...
Kuifje's user avatar
  • 13.5k
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$$
user1502040's user avatar
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?
rocarvaj's user avatar
  • 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 ...
RobPratt's user avatar
  • 32.3k
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$, ...
LarrySnyder610's user avatar
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 ...
Kevin Dalmeijer's user avatar
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) \...
RobPratt's user avatar
  • 32.3k
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=...
Kuifje's user avatar
  • 13.5k
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\...
Kuifje's user avatar
  • 13.5k
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 ...
YukiJ's user avatar
  • 2,023
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 ...
prubin's user avatar
  • 39.3k
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 ...
Oguz Toragay's user avatar
  • 8,652

Only top scored, non community-wiki answers of a minimum length are eligible