31 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 ...
21 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 ...
17 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,512
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 ...
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 ...
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

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 \...
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,225
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 ...
  • 23.4k
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 ...
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 ...
  • 23.4k
11 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 + ...
  • 23.4k
10 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,...
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\...
  • 10.9k
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 ...
  • 23.4k
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$, ...
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
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 ...
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=...
  • 10.9k
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 ...
  • 1,943
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,350
8 votes

Difference between Chance constraints and logical constraints

Logical constraints do not involve probability, except perhaps for the implicit probability of one or zero. Chance constraints specify conditions (constraints) which must hold with a(t least) ...
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 ...
  • 32k
8 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) \...
  • 23.4k
8 votes
Accepted

Can this be formulated as one inequality

It is not possible as a linear inequality in the variables that you provide. Without loss of generality, this linear inequality would be of the form $$y \le \alpha x_1 + \beta x_2 + \gamma.$$ ...
8 votes
Accepted

If else condition to MILP

Let $L$ be a constant lower bound on $X + \sum_j^N G_j$. You want $$X + \sum_j^N G_j \in [L,T-\delta] \cup [T,T]$$ with $c_i=0$ for the first interval and $c_i=1$ for the second (single-point) ...
  • 23.4k
8 votes
Accepted

Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

How about $$\omega_1 + \cdots + \omega_n \le n-1 $$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the ...
  • 10.9k
8 votes

Modeling a constraint such that a set of binary decision variables do not equate to 1 simultaneously

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$ \lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \...
  • 23.4k
8 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 ...
  • 23.4k
7 votes

What is the difference between integer programming and constraint programming?

There were times when the IP and CP communities started to learn about the existence of the other, and initially, people tried to build a list of vocabulary to translate one concept into another. You ...

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