29
votes
Accepted
Why is it important to choose big-M carefully and what are the consequences of doing it badly?
The following answer presumes some familiarity with the limitations of floating-point arithmetic (rounding, truncation and representation errors), which I will lump together as “rounding error”. It is ...
- 37.5k
24
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 ...
- 13k
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 ...
- 12.8k
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 ...
- 12.8k
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,333
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,727
13
votes
Why is it important to choose big-M carefully and what are the consequences of doing it badly?
Tightening the big-M is very important, but sometimes this is done in a reasonable way by the automatic MIP preprocessor.
If you want to see how the BigM in the input model is automatically tightened ...
- 1,646
11
votes
Linear programming: objective function with "buckets"
1. Your suggested approach : quadratic program
Here are the details of your suggested approach. It results in a quadratic objective.
Let binary variable $y_{i,b}$ indicate whether $A_i$ is in bucket $...
- 29.8k
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 ...
- 1,885
11
votes
Accepted
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
Your second if-then statement is always true because $Y$ is binary. For your first if-then statement, rewrite as its contrapositive $Y=0 \implies tS \ge \epsilon$. The following big-M constraint ...
- 29.8k
10
votes
The effect of choosing big M properly
The bigger the big-M is, more likely the numerical issues will happen with solvers.
If you have right hand sides around $10^{10}$ and objective function coefficients in the range of $10^{-2}$, then ...
- 201
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
...
- 12.8k
10
votes
Accepted
If-Then-Else modeling in MILP using the Big M method
There is some ambiguity about the strictness of above/beneath, but does the following do what you want?
$$
0y_1 + Ay_2 + By_3 \le x \le Ay_1 + By_2 + Cy_3 \\
y_1 + y_2 + y_3 = 1
$$
Checking, we have:
\...
- 29.8k
10
votes
Accepted
Formulating two non-negative variables without binary and/or big-M
The big-M values need not be the same. You should choose $M_1$ in $(1)$ to be a small upper bound on $q$ and $M_2$ in $(2)$ to be a small upper bound on $p$.
An alternative formulation is $p q = 0$, ...
- 29.8k
9
votes
Accepted
9
votes
The effect of choosing big M properly
I often see people set $M$ to something like $10^{12}$, when the rest of the model is on the order of $10^2$, because they got the message that $M$ should be "a large constant". Reducing $M$ to ...
- 13k
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
8
votes
Linear programming: objective function with "buckets"
You can add the following equations to your model :
First, define your variable $A_i$:
$$
A_i = \sum_{k}x_k C_{ik}q_k \quad \forall i
$$
Then, define binary variables $y_{ij}$ that take value $1$ ...
- 12.8k
8
votes
Accepted
How to find the index of the item, the first time appears?
Here's a formulation if at least one $x_i$ must be $1$:
\begin{align}
\sum_i y_i &= 1 \tag1\label1\\
y_i &\le x_i &&\text{for all $i$} \tag2\label2\\
y_i &\le 1-x_j &&\text{...
- 29.8k
7
votes
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Another resource is "Strategies for “Not Linear” Optimization" from the AMPL group.
- 8,187
7
votes
Accepted
Integer programming example clarification
You can choose large numbers for your $M$s (big-M) (that's why they are called that), but you also want to make sure they are not very large. See the discussions here and here for the reasons.
In ...
- 5,806
7
votes
Accepted
How is Big M calculated?
There is no incentive to have both $0.40x_1 > 80000$ and $0.30x_1 > 50000$ because then both of the pollutant removal constraints are oversatisfied, so you can take $$x_1 \le \max(80000/0.40,...
- 29.8k
7
votes
Accepted
How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$
If $A\in[\underline{A},\overline{A}]$ and $B\in[\underline{B},\overline{B}]$, the following big-M constraints enforce $Y=1\implies A \le B$ and $Y=0\implies B \le A$, respectively:
\begin{align}
A - B ...
- 29.8k
7
votes
Accepted
Linearizing objective function with variables inside an indicator function
The usual big-M approach would impose two sets of inequalities:
\begin{align}
\sum_j x_j z_{i,j}-v_i &\le \left(\sum_j \overline{x}_j z_{i,j}-v_i\right)(1-w_i)\\
v_i+\epsilon-\sum_j x_j z_{i,j}&...
- 29.8k
7
votes
Accepted
Disjunctive equality constraints: modelling
You do not need another variable. Your disjunction is equivalent to $$x=1 \implies \sum_{i=1}^n y_i = 3,$$ which you can enforce via big-M constraints
$$M_1(1-x) \le \sum_{i=1}^n y_i - 3 \le M_2(1-x)....
- 29.8k
7
votes
How to find the index of the item, the first time appears?
Suppose the index is 1-based and set constant $u_0 = 0$. With binary variables $u_i, y_i, i=1,\dots,n$ and constraints
$$
\begin{align}
u_i &\geq x_i\\
u_i &\geq u_{i-1}\\
u_i &\leq x_i + ...
- 1,026
6
votes
Accepted
Problem with big-M in CPLEX OPL
It is numerically safer to use a (small) data-dependent value for $M$. For your case, rewrite as:
...
- 29.8k
6
votes
Accepted
Converting if else condition to MIP constraints - validation
Looks correct, but there is the usual ambiguity at the boundary: $g=0$ allows either $e$ value. Also, if $b$ is a constant, you can simplify by replacing (3) and (4) with a single equality:
$$e=1\...
- 29.8k
6
votes
Accepted
if-else condition for the objective variable using big M notation
Introduce binary variable $x_{i,j}$ to indicate whether $\beta_{i,j}>0$ and linear constraints:
\begin{align}
\beta_{i,j} &\le x_{i,j}\\
x_{i,j} + x_{j,i} &\le 1
\end{align}
(The big-M here ...
- 29.8k
6
votes
The effect of choosing big M properly
The practical study Analysis of Strength and Weaknesses of a MILP Model for Revising Railway Traffic Timetables includes an analysis of the influence of big M constraints. The conclusion is mixed, ...
- 2,705
Only top scored, non community-wiki answers of a minimum length are eligible