15
$\begingroup$

Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model whether a linear constraint such as $a'x \le b$ should be active in solving (mixed)-integer programs.

What are the best practices for using each? Are there definitive rules to prefer one over the other, or does it depend on the application or implementation? I'd be very interested in explanations of how they are handled in branch-and-bound, as well as any studies reporting empirical evidence.

$\endgroup$
  • $\begingroup$ I'm not sure about the definition of an indicator constraint. Could you edit to elaborate a bit? $\endgroup$ – alerera Jun 4 at 20:51
14
$\begingroup$

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 constraints during the solution process. In this respect, general constraints are just a means of concisely capturing these relationships between variables while removing the burden of creating an equivalent MIP formulation.

Benefit number two - Gurobi may be able to leverage the implicit knowledge of what a constraint actually does in the solving process:

However, general constraints have another potential advantage: Gurobi might be able to simplify parts of the MIP formulation if it can prove during presolve that the simplified version suffices for the correctness of the model. For this reason, Gurobi might be able to produce a smaller or tighter representation of the general constraint than you would get from the most general formulation.

$\endgroup$
15
$\begingroup$

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.

  • A lazy constraint cannot have an indicator constraint.

  • A user-defined cut cannot have an indicator constraint.

  • Only $z=0$ (zero) or $z=1$ (one) is allowed for the indicator variable because the indicator constraint implies that the indicator variable is binary.

Best Practices with Indicator Constraints

  • Avoid Big M values if at all possible. If you choose to introduce Big M values in your model anyway, use the smallest possible value of Big M because Big M values create numerical difficulties and can introduce trickle-flow problems in node LP solutions.

  • Use indicator constraints instead of Big M when Big M values in the formulation cannot be reduced.

  • Do not introduce indicator constraints if Big M can be eliminated from your model.

  • Do not introduce indicator constraints if Big M is eliminated by preprocessing. Check the presolved model to determine whether Big M has been eliminated from your model by preprocessing. In that case, do not introduce indicator constraints for that Big M.

  • If valid upper bounds on continuous variables are available, use them. Bounds strengthen LP relaxations. Bounds are used in a MIP for fixing and so forth.

Further Advice:

Difference between Using Indicator Constraints and a Big-M Formulation

Big-M formulations are relatively straightforward, but the value of the $M$ term needs to be chosen carefully. If $M$ is smaller than the upper bound of $x$, this situation may cut off valid solutions. If $M$ is too large, the model may become numerically difficult or exhibit trickle flow.

Indicator constraints have the advantage of avoiding these types of problems, as they do not rely on a separate constant value. However, they tend to have weaker relaxations during the MIP optimization, a condition which may lead to longer solve times in a model.

Consider using the big-M form instead of indicators:

  • When the big-M factor is not much larger than other coefficients in the model.
  • If the big-M factor is eliminated in presolve. You can write out the presolved model to check this condition.
  • If the model does not show any side effects from a big-M formulation.
  • If [the solver] can not efficiently solve the model formulated with indicator constraints.

Consider using indicator constraints instead of big-M:

  • When the big-M factor remains very large, relative to other coefficients in the model.
  • When the big-M formulation is difficult to express, such as an if-then constraint on complex expressions.

In all cases, defining upper bound information on the continuous variable will generally yield a much tighter formulation and nearly always helps with performance.

I will have to defer to someone else as to how indicator constraints are handled internally in the solver, for instance in CPLEX, and to what extent SOS may or may not be involved.

Big M formulations are subject to logic "errors" due to "trickle flow". See

I will update this answer based on any answer I get to a question Are indicator constraints immune to trickle flow or other numerics-induced logic 'errors'? which I just posted on the CPLEX forum.

EDIT: Indicator Constraints in CPLEX are immune from the big M/trickle flow issue. I have placed the details, provided Ed Klotz of IBM, in a separate answer to this question.

$\endgroup$
  • $\begingroup$ I wonder whether there is really a computational disadvantage with big-M if M is tight (I.e. as low as possible). My intuition tells me that that should not really have a worse (maybe even better) performance than indicators. But I haven’t checked, has anybody anecdotally? $\endgroup$ – Richard Jun 5 at 14:16
  • 1
    $\begingroup$ I'm not sure how much I trust the advice to use indicators in preference to big-M if M cannot be "reduced" (from what to what?). Years ago, I attended an IBM workshop at an INFORMS conference. One of their people (whose expertise I trust) said that if you can come up with reasonably tight values of $M$ (I'm paraphrasing here) based on your knowledge of the problem, that would be preferable to indicator constraints. I assume that if you're just going to plop down an arbitrarily large power of 10, indicators are preferable. $\endgroup$ – prubin Jun 5 at 23:24
  • $\begingroup$ @prubin Can you give us some insight as to how indicator constraints are handled( nternally by (or formulated for) solvers, for example CPLEX, or any others you are familiar with? Perhaps post it as a separate answer. $\endgroup$ – Mark L. Stone Jun 5 at 23:29
  • $\begingroup$ In SCIP, I think that the indicator constraint may be able to dynamically strenghten the linear relaxation during the solve process, whenever the bounds of the relevant variables are tightened (can not find a reference at the moment). In that sense, the formulation might be better even if the user was able to choose the best M in the beginning. $\endgroup$ – Robert Schwarz Jun 6 at 7:55
  • $\begingroup$ @MarkL.Stone I'm not familiar with other solvers, and I'm not privy to the (proprietary) inner workings of CPLEX. From a talk given by IBM reps and other conversations, I think CPLEX handles them at least partially as big M constraints, where CPLEX deduces a suitable value of M. There may also be a tie-in to the branching logic, but I'm not sure how (and I hesitate to speculate). $\endgroup$ – prubin Jun 7 at 3:35
12
$\begingroup$

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 have. Then it very likely that your custom made big-M formulation yields a better bound compared to the automatically generated reformulation.

See also the discussion here: Why is it important to choose big-M carefully and what are the consequences of doing it badly?

$\endgroup$
  • $\begingroup$ I was formulating my answer when you posted this. I thought I saw something pertaining to restrictions in CPLEX on the use of indicator constraints relating somehow to SOS, but now I can't find it, so don't know how it does or does not correspond to CPLES using SOS to handle indicator constraints. $\endgroup$ – Mark L. Stone Jun 5 at 11:41
  • 1
    $\begingroup$ See the gurobi manual (gurobi.com/documentation/8.1/refman/…) for their description on the max constraint. I'd guess that indicator constraints are handled similarly. $\endgroup$ – JakobS Jun 5 at 11:47
  • 1
    $\begingroup$ I just asked a question on the CPLEX forum ibm.com/developerworks/community/forums/html/… about whether indicator constraints can experience trickle flow or similar logic error. I will report back with any answer. $\endgroup$ – Mark L. Stone Jun 5 at 12:12
  • 1
    $\begingroup$ Indicator Constraints in CPLEX are not just syntactic sugar. See my updated answer on this thread, $\endgroup$ – Mark L. Stone Jun 8 at 10:31
  • $\begingroup$ Nice find. The same does seem to hold for gurobi (probably for other solvers as well). I learned something today :) $\endgroup$ – JakobS Jun 11 at 7:52
7
$\begingroup$

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 the value of the integrality tolerance, trickle flow can result in the intended logic of Big M constraints not being satisfied.

Can indicator constraints ever be violated due to a similar phenomenon? Does integrality tolerance come into play? What if due to large bounds on involved variables, M in a Big M constraint would have to be very large - can indicator constraints get into trouble (not just slow solution, but wrong solution) if they are used in lieu of Big M constraints in such a situation? Does the setting of integrality tolerance have any effect on whether indicator constraints can produce the wrong solution?

Answer by Ed Klotz of IBM:

Here some details in addition to the IBM Technote: Difference between using indicator constraints and a big-M formulation . First, indicator constraints are indeed completely immune to the trickle flow issue associated with big M formulations. But there still is a trade off, although the downside has definitely been diminished since indicator constraints first appeared around CPLEX 10.0. Namely, the relaxation of an indicator constraint is obtained by removing the indicator constraint, solving the associated relaxation, then branching on violated indicator constraints. For huge big M values, this is not really a drawback. But for modest values of big M of say 100000, which can still potentially have trickle flow issues, this can result in a weaker formulation. Recent versions of CPLEX have made improvements in indicator probing and other MIP preprocessing that typically reduce the burden on the user to decide between an indicator and big M formulation that is described in the above technote. If CPLEX can detect reasonable bounds on the variable or expression implied by the indicator variable, then it will probably be able to tighten the formulation for you, and you don't need to worry about the potential weakness. But if the variable or expression implied by the indicator variable have implicit modest bounds that involve a very complex combination of constraints that elude CPLEX's bound strengthening and other MIP preprocessing methods, then you might want to consider supplying those bounds yourself in the formulation to tighten it.

Slides 19-23 of Klotz and Wunderling:Tools for Adapting Math Programming Solutions in the Real World may help a bit; the info is similar to the content of the above technote, but it does provide a few more details.

Note the following useful tips from slide 20 of Klotz and Wunderling:Tools for Adapting Math Programming Solutions in the Real World

To get correct answers with big-M

  • Use smallest possible value of big-M that doesn’t violate intent of model
    • Bound strengthening in CPLEX presolve often does this automatically
  • Set integrality tolerance to 0
  • Set simplex tolerances to minimum values, 1e-9
  • Ask for more accuracy on an ill-conditioned system
    • Turn on numerical emphasis parameter
$\endgroup$
  • 2
    $\begingroup$ Given the trade-offs indicated by Ed Klotz, one might wonder: "Why not both"? That is, add the big-M for the strenghthened LP relaxation and the indicator for the "clean" branching effect. $\endgroup$ – Robert Schwarz Jun 11 at 5:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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