19 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 ...
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 - ...
user avatar
  • 1,323
13 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 ...
user avatar
  • 2,677
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 ...
user avatar
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) \...
user avatar
  • 22.7k
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 ...
user avatar
  • 10.4k
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 ...
user avatar
  • 31k
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 ...
user avatar
  • 22.7k
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 &\...
user avatar
  • 22.7k
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 < ...
user avatar
  • 3,487
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 \...
user avatar
  • 22.7k
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+\...
user avatar
  • 22.7k
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 ...
user avatar
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$.
user avatar
  • 22.7k
6 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 ...
user avatar
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 &...
user avatar
  • 22.7k
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 ...
user avatar
  • 22.7k
5 votes

Model "If, then" constraint

in OPL CPLEX you could directly use logical constraints and write ...
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.
user avatar
  • 22.7k
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 \...
user avatar
  • 22.7k
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....
user avatar
  • 31k
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 \...
user avatar
  • 22.7k
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 &...
user avatar
  • 22.7k
4 votes
Accepted

Switching of decision variables to be equal to a certain decision variable according to a binary (indicator) variable

$$ x \le z + M(1-\beta) \\ x \ge z - M(1-\beta) \\ x' \le z + M\beta \\ x' \ge z - M\beta \\ $$ If $\beta=1$, we have $$ x \le z \\ x \ge z \\ x' \le z + M \\ x' \ge z - M \\ $$ which leads to $x=z$ ...
user avatar
  • 10.4k
4 votes
Accepted

Reformulating to locate the second largest decision variable of a set of decision variables

To get the second largest variable when all are nonnegative and at most two can be nonzero, just take the sum of all of them and subtract the largest.
user avatar
  • 22.7k
4 votes

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

I would like to remind that CPLEX can handle "if then" directly through logical constraints. In OPL for example: ...
user avatar
4 votes
Accepted

MILP constrained by the minimum number of satisfied constraints

You can introduce a binary variable $x_k$ and linear constraints \begin{align} \sum_k x_k &\ge N\tag1\\ -t_k+T_k&\le M_k(1-x_k) &&\text{for $k\in K$}\tag2 \end{align} Here, the “big-M” ...
user avatar
  • 22.7k
4 votes
Accepted

How to couple a binary variable to a continuous variable to indicate values greater 0

I'm only aware of a mechanism that works if there is an upper bound for the continuous variable. \begin{align}x_{t, \max}\cdot b_t &\geq x_t\\ m\cdot x_t &\geq b_t\end{align} I used this in ...
user avatar
4 votes

How to couple a binary variable to a continuous variable to indicate values greater 0

Enforcing $b_t$ to take value $1$ when $x_t$ is positive is done with $x_t \le b_t$, assuming $x_t \le 1$. For the second part, quoting @MarkL.Stone: You will have to choose a tolerance as to how ...
user avatar
  • 10.4k
4 votes

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

Finding all optima of a linear program can be NP-annoying, so finding the optimum with the most binding constraints is likely also NP-annoying. The multiple optima will be vertices of a facet of the ...
user avatar
  • 31k

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