23
$\begingroup$

The question here discusses the two different use of "big-M method", where one of them is the big-M in logical constraints and linearization in (mixed-)integer programming problems (that's what I'm interested in).

Then, the question here asks about the effects of big-M and I'm aware that a choice of a very large M (of course, large relative to the problem) can create a model with weak relaxations which in turn, may make the model hard for the solvers. So, my question is how can I choose big-M properly and what are the (other) consequences of a poor choice?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ In my answer at or.stackexchange.com/questions/57/… I mention the possibility of M being large enough relative to solver integrality tolerance to invalidate the intended logic of the Big M modeling. See also @prubin 's blog post linked there, orinanobworld.blogspot.com/2018/04/… .So if appropriate care is not taken, rather than just making solution process slower due to weak relaxations, the answer produced by the solver might be wrong, relative to the intended model $\endgroup$
    – Mark L. Stone
    Jun 4, 2019 at 19:05
  • $\begingroup$ this calls for a machine learning approach :) $\endgroup$
    – Marco Lübbecke
    Jun 7, 2019 at 21:04

2 Answers 2

Reset to default
29
$\begingroup$

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 $a'x\le b+My$ illustrates the situation where $M$ shows up as a coefficient in the constraint matrix. This is where serious misadventures can occur. If $M$ appears in the basis matrix, rounding errors can make the basis look singular or make a column that should be ineligible for entry to the basis look eligible. The rounding errors can also cause severe loss of precision in the computation of the basic feasible solution. In technical terms, $M$ (or $1/M$) appearing in the basis matrix can make it ill-conditioned.

Even if ill-conditioned basis matrices do not occur, large values of $M$ can cause branch-and-bound solvers to make slow progress solving the mixed-integer programming model (MIP). Consider the constraint $x_{ij}-My_{j}\le0$, where $x_{ij}$ is the flow of some commodity $i$ across and arc $j$, and $y_{j}$ is a binary variable indicating the presence or absence of that arc. There will be an associated penalty cost (say, $c_{j}y_{j}$) in the objective function for providing arc $j$. Now suppose that, at some point, the solver is considering a node in the search tree where $x_{1j}=2$, $x_{2j}=5$ and $x_{ij}=0$ for other values of $i$. Logically, we know this requires $y_{j}=1$ and incurs cost $c_{j}$; but in the LP-relaxation of the node problem, $y_{j}=5/M$ is sufficient, incurring a cost of just $5c_{j}/M$. For large values of $M$, this substantially underestimates the true cost, leading to loose node bounds. Loose bounds at nodes, in turn, make it hard for the solver to prune nodes based on objective value, and so more nodes need to be examined, slowing the solution process.

The previous example also reveals another problem. Solvers have a tolerance for how close a variable value needs to be in order to consider it an integer. If $5/M$ is small enough, a solver may consider $y_{j}=5/M$ to be an integer (zero) and accept the solution as integer-feasible, when clearly it is not.

Choosing a value for $M$

There are several considerations when choosing values for $M$.

• You want the smallest value of M that is large enough to avoid cutting off a legitimate solution. If $M$ is chosen too small in $a'x\le b+My$, a valid choice of $x$ may violate the constraint even when $y=1$.

• On paper, “big M” models usually use a single symbol $M$ in every constraint. This is usually laziness by the authors. In practice, constraint-specific values of $M$ should be chosen.

• Calibrating $M$ is generally problem-specific. For constraints like $a'x\le b+My$, one possibility is to relax the integrality constraints and maximize $a'x-b$ subject to the other constraints (relaxing others by setting the binary variables to whichever value makes the constraints looser). Done properly, the maximum objective value should provide a safe choice for $M$ (though not necessarily the tightest safe choice).

• There may be context-specific ways to choose a safe value for $M$. An example of one, in the context of discriminant analysis, is in one of my old papers [2].

Alternatives to $M$ models

For situations where constraints need to be turned on or off using binary variables, a possible alternative is “combinatorial Benders decomposition” [3]. This is not automatically superior, but can be effective in some cases.

Some solvers (including but not limited to CPLEX and SCIP) provide “indicator constraints” or “if-then” constraints. The preceding example, posed as an indicator constraint, would essentially be $y_{j}=0\implies x_{ij}=0$. It is up to the solver designers how to process such constraints, but frequently they will simply turn into “big M” constraints with the solver selecting a value for $M$. Even if that does not happen, indicator constraints may weaken LP relaxations.

References

[1] Rubin, Paul. “Perils of 'Big M'.” OR in an OB World, 11 July 2011, https://orinanobworld.blogspot.com/2011/07/perils-of-big-m.html.

[2] Rubin, P. A. (1990). Heuristic Solution Procedures for a Mixed-Integer Programming Discriminant Model. Managerial and Decision Economics 11, 255-266.

[3] Codato, G. & Fischetti, M. (2006). Combinatorial Benders' Cuts for Mixed-Integer Linear Programming. Operations Research 54, 756-766.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Nice answer. But let's say we need to have a model which intrinsically needs to have a large M, but we have chosen the integrality tolerance small eouugh so that worst case integrality violation (considered to be integer by the solver) ensures correct logic in the constraints. But what about presolve? Can presolve change the model so that a model which appeared to be solid from integrality tolerance not causing constraint logic "error" standpoint isn't, because the constraints and variables are different than those in the model the user entered? $\endgroup$
    – Mark L. Stone
    Jun 4, 2019 at 19:50
  • 1
    $\begingroup$ Good question. I suspect that it's possible. I've seen instances where presolve mucked up a model, probably including (but definitely not limited to) "big M" sorts. I don't know whether arithmetic adventures with large coefficients contributed to the presolved model going sideways, but it would not shock me if that happened. $\endgroup$
    – prubin ♦
    Jun 5, 2019 at 10:12
  • 1
    $\begingroup$ Please keep in mind that disjunctions that lead to Big-M formulation can be also formulated using the Hull-relaxation. This formulation involved adding extra continuous variables but removes the requirement for Big-M parameters in general. This reformulation arises from Balas' characterization of disjoint polyhedra. $\endgroup$
    – David Bernal
    Jun 5, 2019 at 19:18
  • 1
    $\begingroup$ @MarkL.Stone I doubt it. I think you can write the presolved model in LP (text) format. I've never tried it, so I don't know exactly what to expect, but I would not be shocked if some constraint names (and maybe some variable names) were CPLEX-generated. It should be tedious but straightforward to see if all "M" coefficients were gone (just verify that no coefficient has a big exponent field). If there are still big coefficients left, though, what could you infer about trickle? $\endgroup$
    – prubin ♦
    Jun 5, 2019 at 20:42
  • 3
    $\begingroup$ Just a provocative remark: the issue with bigM is not solved if it becomes small, the problem is that the corresponding constraint is unlikely to be tight at the optimum. Of course, smaller bigM’s are useful to improve a bit the lower bound, but if this bound remains poor you have no other option than branching and refine the bigM locally (I.e. tighten the bigM for the subproblem at hand). This is done customary by nonlinear solvers e.g. with the bigM’s involved in the McCormick linearization of bilinear terms. $\endgroup$
    – Matteo Fischetti
    Jun 8, 2019 at 12:42
13
$\begingroup$

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 quit Cplex and text-edit preprocessed.lp.

In any case, the big-M in the formulation is typically chosen to be “globally” valid for any feasible solution, hence it cannot be very effective. Much better “local” big-M values can be computed along the decision tree due to the branching conditions, meaning that the corresponding constraint eventually becomes tight at the optimal solution.

See e.g.

http://www.dei.unipd.it/~fisch/papers/indicator_constraints.pdf

for a discussion

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.