Hot answers tagged

29

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 a trimmed down version of a longer blog post [1] with more detail and some astute comments from subject matter experts. $M$ in the constraints The constraint ...


21

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 for finding an initial feasible solution for the simplex method. (Another common method for doing this is the two-phase method.) Sometimes people also use the ...


18

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 situations: Indicator Constraints in Optimization The constraint must be linear; a quadratic constraint is not allowed to have an indicator constraint. ...


17

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 document and then addressing any particular difficulties or concerns the questioner may have. FICO MIP formulations and linearizations Quick reference at https://www....


15

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 - models are easier to create and can be interpreted easily: If a model contains general constraints, then Gurobi adds the respective MIP formulations for those ...


13

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 constraints (special ordered set constraints). It might be that you are better at computing the value of the big-M using additional knowledge that the solver does not ...


12

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 by Cplex, in interactive mode you can use the following series of commands: read originalproblem.lp write a.pre read a.pre write preprocessed.lp and then ...


11

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 citation below. [1] Gerald G. Brown, Robert F. Dell, (2007) Formulating Integer Linear Programs: A Rogues' Gallery. INFORMS Transactions on Education. 7(2):...


11

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 enforces that: $$\epsilon - tS \le MY$$ This is equivalent to what you tried. Note that $(tS,Y)=(\epsilon,0)$ is feasible, so if the solver always returns it, ...


10

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 $b$, where $b\in\{1,2,3\}$. Let $M_i$ be a (small) upper bound on $A_i$. The constraints are: \begin{align} \sum_{b=1}^3 y_{i,b} &= 1\\ 10 y_{i,1} + 8 y_{i,2}...


10

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 solvers will have hard time dealing with such big range of values. And big-M's are the usual suspects in such situations. So smaller the big-M, tighter and ...


10

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 numerics-induced logic "errors"? As discussed at IBM Technote: Why does a binary or integer variable take on a noninteger value in the solution?, depending on ...


10

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$, but that is nonlinear. If your solver supports indicator constraints, you can write the desired implications directly, without specifying big-M: \begin{align} y ...


9

Equivalently, $c=\max(a,b)$. See this post.


9

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 something several orders of magnitude smaller then does have a noticeable impact on the run time. My point is: Once you know that you should should be careful about ...


9

What about Mixed Integer Linear Programming Formulation Techniques, J.P. Vielma, SIAM Rev., 57(1), 3–57, 2015?


7

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 your example, your big-Ms just need to be bigger than the upper bound of the values that the variables can take (as @Stradivari mentioned). So, for each of $x_1, ...


7

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,50000/0.30) = 200000.$$ Similarly, \begin{align} x_2 &\le \max(80000/0.25,50000/0.20) = 320000 \\ x_3 &\le \max(80000/0.20,50000/0.25) = 400000 \end{align}...


7

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$ iff $A_i$ is in interval $j$ (where interval $1$ is $[0,100]$, interval $2$ is $[101,200]$, and interval $3$ is $[201, \infty[$ : \begin{align} 0 &\le A_i \...


7

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 &\le (\overline{A}-\underline{B})(1-Y)\\ B - A &\le (\overline{B}-\underline{A}) Y\\ \end{align} To disambiguate the $A=B$ case, you could introduce $\...


7

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}&\le \left(v_i+\epsilon-\sum_j \underline{x}_j z_{i,j}\right)w_i \end{align} To linearize the objective function, replace the denominator with $n$.


7

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: \begin{align} y_1 = 1 &\implies x \in [0,A] \\ y_2 = 1 &\implies x \in [A,B] \\ y_3 = 1 &\implies x \in [B,C] \\ \end{align}


6

It is numerically safer to use a (small) data-dependent value for $M$. For your case, rewrite as: C[i][k] + TaskTime[j][k] - C[j][k] <= M[i][j][k] * (1 - X[i][j]); You want to choose $M_{i,j,k}$ to be a (small) upper bound on the left hand side when $X_{i,j}=0$. A good choice is $$M_{i,j,k} = U_{i,k} + T_{j,k} - L_{j,k},$$ where $U_{i,k}$ is a good ...


6

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\delta+b(1-\delta)$$ Note that the best values of $M$ in (3) and (4) yield this equality. Explicitly: \begin{align} 1-(1-b)(1-\delta) &\le e \le 1+(b-1)(1-\...


6

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 is 1.) The first constraint enforces $$\beta_{i,j}>0 \implies x_{i,j} = 1.$$ The second constraint enforces $$x_{i,j} = 1 \implies x_{j,i} = 0.$$ The first ...


6

Another resource is "Strategies for “Not Linear” Optimization" from the AMPL group.


6

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, though: in their model, knowledge of sharp M-values has a notable effect, but sharp values are obviously hard to find in practice.


6

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$.


6

As Sune said in a comment, they really are both "big-M" constraints, differing (perhaps) in how "big" $M$ is. If you choose $M$ sufficiently large, then yes, your second constraint will not meaningfully limit the values of the $x$ variables ... which likely is by design. Other constraints in the model will probably restrict the values of ...


6

If you want $z=\max(a_1,\dots,a_n)$, you can first enforce $z\ge\max(a_1,\dots,a_n)$ via linear constraints: \begin{align} z &\ge a_i &&\text{for all $i$} \tag1 \end{align} If you cannot rely on the objective to also enforce $z\le\max(a_1,\dots,a_n)$, let $M$ be a small constant upper bound on $z$, let $\ell_i$ be a constant lower bound on $a_i$, ...


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