Skip to main content
20 votes

When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

Here is the advice in the IBM CPLEX documentation. So this pertains to CPLEX. I don't know to what extent it applies to other solvers. First of all, indicator constraints may not be available in all ...
Mark L. Stone's user avatar
17 votes
Accepted

When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

For Gurobi there seems to be a dual advantage of using general constraints (http://www.gurobi.com/documentation/8.1/refman/constraints.html#subsubsection:GeneralConstraints): Benefit number one - ...
CMichael's user avatar
  • 1,333
14 votes

When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

To the best of my knowledge the indicator constraints are just syntactic sugar for the user. Internally these indicator constraints are reformulated using computed big-M formulations or SOS ...
JakobS's user avatar
  • 2,757
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.4k
10 votes

When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

Question by me at the IBM CPLEX Forum: Are indicator constraints immune to trickle flow or other numerics-induced logic "errors"? Are indicator constraints immune to trickle flow or other ...
Mark L. Stone'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
  • 32k
8 votes
Accepted

how can I modify my LP to activate the most constraints possible?

Suppose your problem is of the form $\min c^Tx$ subject to $Ax+e =b$, where $e$ denotes the slack variables. You could proceed in two steps. Solve the initial LP. Let $z^*$ be the value of the ...
Kuifje's user avatar
  • 13.4k
7 votes

Faster implementation of "or" constraints in ILP

Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are ...
RobPratt's user avatar
  • 32k
7 votes
Accepted

Indicator function in math programming

Introduce binary variable $y_0$ and linear constraints: \begin{align} y_0 + y_1 + y_2 &= 1\\ 1y_0 + 2y_1 + 3y_2 &= x \end{align} Equivalently, eliminating $y_0$: \begin{align} y_1 + y_2 &\...
RobPratt's user avatar
  • 32k
7 votes
Accepted

How to convert this if-then constraint to MIP constraint?

$a \geq M_1x$ $a \leq M_2 - (M_2+eps)x$ $b = K_1 + (K_2-K_1)x$ $M_1 < 0$ bigM for the lower bound on $a$ $M_2 > 0$ bigM for the upper bound on $a$ $x$ binary variable equal to $1$ if $a < ...
user3680510's user avatar
  • 3,655
7 votes
Accepted

How are indicator constraints implemented?

You can have a look at SCIP's implementation in cons_indicator. They say that: An indicator constraint is given by a binary variable $z$ and an inequality $ax \le b$. It states that if $z=1$ then $ax ...
Robert Schwarz's user avatar
7 votes
Accepted

Representing an indicator function: binary variables and "indicator constraints"

First question: Yes, your algebraic formulation is correct. Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader ...
prubin's user avatar
  • 39.2k
7 votes
Accepted

If-then constraint with continuous variables

Introduce a binary variable $y_{i,j}$ and linear constraints \begin{align} x_{i,j} &\le M y_{i,j} \tag1 \\ y_{i,j} + y_{j,i} &\le 1 \tag2 \end{align} Constraint $(1)$ enforces $x_{i,j} > 0 \...
RobPratt's user avatar
  • 32k
7 votes
Accepted

Model "if and only if" indicator constraints in Linear programming

Without using a small epsilon, you can’t enforce strict inequality. Here’s one approach that allows ambiguity at the endpoints of each interval, as your proposed constraint does: $$ x+y+z=1\\ 0x+\...
RobPratt's user avatar
  • 32k
7 votes
Accepted

If-then condition formulation to avoid variable multiplication

Something like: $$\begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align}$$ $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using ...
Erwin Kalvelagen's user avatar
7 votes
Accepted

How to enforce logical implication $\sum_j a_j x_j \le b \implies \sum_j c_j x_j \le d$

You can accomplish this by introducing a binary decision variable and splitting into two implications: \begin{align} \sum_j a_j x_j \le b &\implies y = 1 \tag1\label1 \\ y = 1 &\implies \sum_j ...
RobPratt's user avatar
  • 32k
7 votes

Rewriting if-then constraints of binary summations

@Kuifje gave a correct formulation without introducing additional variables. To answer your question about the indicator variable approach, what you proposed is not correct. To enforce $$\sum_b x_{i,j}...
RobPratt's user avatar
  • 32k
6 votes
Accepted

Formulating the conditional constraint

Let $M_i$ be an upper bound on $Q_i$, and impose linear big-M constraints $0 \le Q_i \le M_i x_i$.
RobPratt's user avatar
  • 32k
6 votes

Is this constraint with an indicator function nonlinear?

Indicator constraints are not linear constraints, but here’s a linearization with binary variables $z_i$: \begin{align} \sum_i z_i &= 1 \\ \sum_i i z_i &= y \\ \sum_i c_i z_i &= x \end{...
RobPratt's user avatar
  • 32k
5 votes
Accepted

How to fomulate the following conditional constraint in MILP?

Here's a big-M formulation that does not depend on the objective. (Minimization with positive objective coefficients for $u$ and $d$ could be exploited, but you don't have that here.) Let $\epsilon &...
RobPratt's user avatar
  • 32k
5 votes

Model "If, then" constraint

in OPL CPLEX you could directly use logical constraints and write ...
Alex Fleischer's user avatar
5 votes
Accepted

Linearize sum of continuous and boolean variable

If $M$ is a (small) upper bound on $x$, introduce a binary variable $z$ and big-M constraint $x \le M z$. The idea is that $x>0$ implies $z=1$. Now use $B z$ in the objective.
RobPratt's user avatar
  • 32k
5 votes

Portfolio optimization with indicator function constraint in CVXPY

I assume that $w_i$ is a continuous variable with $0 \le w_i \le 1$ and $w_i^\text{start}$ is a constant with $0 \le w_i^\text{start} \le 1$. You want to enforce $$|w_i-w_i^\text{start}| > 0 \...
RobPratt's user avatar
  • 32k
5 votes
Accepted

How to model this chain of logical implication II

You can use conjunctive normal form to derive the desired constraints. The first one is: $$a \ge b \implies a\ge c\\ (b \implies a) \implies (c \implies a)\\ \lnot(\lnot b \lor a) \lor (\lnot c \lor ...
RobPratt's user avatar
  • 32k
5 votes
Accepted

Logical equivalencies to modeling an indicator decision variable in transportation problem

Consider the following tiny example. You have two factories, one warehouse and two product. Factory 1 can produce both goods in sufficient quantity to meet demand but has a very large cost coefficient....
prubin's user avatar
  • 39.2k
5 votes
Accepted

Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary

Equivalently, you want to enforce the contrapositive $y = 1 \implies x > 0$. The standard approach is to introduce a small constant tolerance $\epsilon > 0$ and enforce $y = 1 \implies x \ge \...
RobPratt's user avatar
  • 32k
5 votes
Accepted

Piecewise function with two variables

You have a disjunction of four polyhedra $A_i x \le b_i$. Introduce four binary variables $r_i$ (one per region) and impose linear constraints: \begin{align} \sum_{i=1}^4 r_i &= 1 \\ A_i x - b_i &...
RobPratt's user avatar
  • 32k
5 votes
Accepted

Is this constraint with an indicator function nonlinear?

Since the constraint includes binaries, it does not define a convex set, and is therefore not linear. For example, if $x=c_11_{A}$, $x$ can take values either $0$ or $c_1$. But $\frac{0+c_1}{2} \notin ...
Kuifje's user avatar
  • 13.4k
5 votes
Accepted

Using indicator constraint with two variables

You want to enforce $x+y=1 \implies z \le 20$. Introduce a new binary variable $w$ and enforce \begin{align} x+y = 1 &\implies w = 1 \tag1\label1\\ w = 1 &\implies z \le 20 \tag2\label2\\ \...
RobPratt's user avatar
  • 32k
5 votes
Accepted

if else condition with multiple criteria in MIP

Let $\epsilon$ be a small constant positive tolerance, and let $M$ be a constant upper bound on $x_1$. Now impose linear constraints $$\epsilon s_1 \le x_1 \le M s_1.$$
RobPratt's user avatar
  • 32k

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