Hot answers tagged

30 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 ...
prubin's user avatar
  • 38.8k
25 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 ...
LarrySnyder610's user avatar
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

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 ...
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,747
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 ...
Matteo Fischetti's user avatar
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 $...
RobPratt's user avatar
  • 31.5k
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 ...
SecretAgentMan's user avatar
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 ...
RobPratt's user avatar
  • 31.5k
11 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$, ...
RobPratt's user avatar
  • 31.5k
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
10 votes
Accepted

Linear programming with if-then-else (big-M)

Equivalently, $c=\max(a,b)$. See this post.
RobPratt's user avatar
  • 31.5k
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 ...
Baykal's user avatar
  • 201
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: \...
RobPratt's user avatar
  • 31.5k
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 ...
LarrySnyder610's user avatar
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?
rocarvaj's user avatar
  • 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$ ...
Kuifje's user avatar
  • 13.2k
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{...
RobPratt's user avatar
  • 31.5k
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.
A.Omidi's user avatar
  • 8,717
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 ...
EhsanK's user avatar
  • 5,864
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,...
RobPratt's user avatar
  • 31.5k
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 ...
RobPratt's user avatar
  • 31.5k
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}&...
RobPratt's user avatar
  • 31.5k
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)....
RobPratt's user avatar
  • 31.5k
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 + ...
xd y's user avatar
  • 1,186
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: ...
RobPratt's user avatar
  • 31.5k
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\...
RobPratt's user avatar
  • 31.5k
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 ...
RobPratt's user avatar
  • 31.5k
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, ...
Marcus Ritt's user avatar
  • 2,715

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