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 ...
- 11.1k
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 - ...
- 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 ...
- 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
...
- 11.1k
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) \...
- 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 ...
- 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 ...
- 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 ...
- 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 &\...
- 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 < ...
- 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 \...
- 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+\...
- 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 ...
- 1,804
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$.
- 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 ...
- 2,275
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 &...
- 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 ...
- 22.7k
5
votes
Model "If, then" constraint
in OPL CPLEX you could directly use logical constraints and write
...
- 3,527
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.
- 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 \...
- 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....
- 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 \...
- 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 &...
- 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$ ...
- 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.
- 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:
...
- 3,527
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” ...
- 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 ...
- 3,527
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 ...
- 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 ...
- 31k
Only top scored, non community-wiki answers of a minimum length are eligible