5
$\begingroup$

I wonder how systems like CPLEX, GUROBI, etc implement indicator constraints. Do they just implement Big M equivalents? If yes, what is then the justification for using them?

Edit

The question does not concern when to prefer using BigM constraints vs Indicator constraints. The question is if the developers of the solver coded the idea of an indicator constraint by coding its equivalent BigM constraint.

$\endgroup$
  • $\begingroup$ See "When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs" or.stackexchange.com/questions/231/… $\endgroup$ – Mark L. Stone Jun 10 '20 at 19:28
  • 1
    $\begingroup$ Hi Rob My question is not really about when to use an indicator constraint vs a BigM constraint. I mean, the developers, for example, of CPLEX have somehow implemented indicator constraints using a programming language. Did they actually implement it as a Big M constraint or in another way? Do you know what is this other way, if it exists? So when I pass to CPLEX an indicator constraint, does CPLEX see nothing else than a BigM constraint? $\endgroup$ – Clement Jun 10 '20 at 19:48
  • $\begingroup$ Hi Rob. From the link you posted I see, that I am actually asking for proprietary information. I thought there is no secret about indicator constraints. Well, I am wrong. $\endgroup$ – Clement Jun 10 '20 at 20:14
  • 1
    $\begingroup$ See this one or.stackexchange.com/questions/231/… of my two answers for somewhat more insight on implementation of Indicator constraints in CPLEX. $\endgroup$ – Mark L. Stone Jun 10 '20 at 20:53
6
$\begingroup$

You can have a look at SCIP's implementation in cons_indicator. They say that:

An indicator constraint is given by a binary variable $z$ and an inequality $ax \le b$. It states that if $z=1$ then $ax \le b$ holds.

This constraint is handled by adding a slack variable $s: ax−s \le b$ with $s \le 0$. The constraint is enforced by fixing $s$ to $0$ if $z=1$.

This constraint is equivalent to a linear constraint $ax−s \le b$ and an SOS1 constraint on $z$ and $s$ (at most one should be nonzero). In the indicator context we can, however, separate more inequalities.

$\endgroup$

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