1
$\begingroup$

Suppose we have two continuous nonnegative variables $X_{1}$ and $X_{2}$ both bounded by the number $M$ from above.

I would like to model the following:

If $X_{1} > 0$ then $X_{2} = 0$

If $X_{2} > 0$ then $X_{1} = 0$

I can do this by imposing $X_{1} X_{2} = 0$ but this is a nonconvex nonlinear term.

I can instead model as follows:

$X_{1} \le M \\ X_{2} \le M \\ X_{1} \le B_{1} M \\ X_{2} \le B_{2} M \\ B_{1} + B_{2} \le 1 $

where $B_{1}$ and $B_{2}$ are binary variables. The result is a MILP.

Can you see an alternative way for modeling this relation?

Improve this question
$\endgroup$
  • $\begingroup$ You can omit the first two constraints, which are implied by the next two. $\endgroup$ – RobPratt Nov 25 '20 at 18:43
  • $\begingroup$ Yes, aber I don't win that much do I? $\endgroup$ – Clement Nov 25 '20 at 18:45
  • $\begingroup$ No, just a little simpler, like omitting $B_1 \le 1$ and $B_2 \le 1$. $\endgroup$ – RobPratt Nov 25 '20 at 20:08
3
$\begingroup$

This type of constraint is called a complementarity constraint, and there are several ways of modeling it, two of them you already mentioned. There is no silver-bullet formulation: some will work better than others depending on your instance, your solver, etc.

Some solvers support complementarity constraints directly, for instance Knitro or PATH.

If you choose the MIP-base route, then an alternative to big-M formulations (the one you proposed above) is to use indicator constraints. The majority of commercial MIP solvers support it, and it can be more efficient than using a big-M.

Improve this answer
$\endgroup$
2
$\begingroup$

You can declare $\lbrace X_1, X_2 \rbrace$ to be a type 1 special ordered set (SOS1). Assuming that your solver understands SOS1 constraints, it will enforce what you want internally, possibly by a "big M" approach and possibly through branching. This again results in a MILP.

Improve this answer
$\endgroup$
  • $\begingroup$ Thank you very much for your suggestion. Is there any reason to believe that the SOS1 approach would work more efficiently than the use of binaries? $\endgroup$ – Clement Nov 26 '20 at 7:51
  • $\begingroup$ If the solver makes branching decisions based on SOS1 constraints, it avoids the introduction of the large "M" coefficient (which can weaken relaxations and possibly cause numerical issues). If the solver uses a "big M" formulation internally, it comes down to whether you or the solver find the tighter value for M. $\endgroup$ – prubin Nov 26 '20 at 17:01
  • $\begingroup$ Now with reference to this link or.stackexchange.com/questions/3104/… the question of which solver supports SOS1 branching arises. $\endgroup$ – Clement Nov 27 '20 at 16:42
  • $\begingroup$ There may also be workarounds involving callbacks. For instance, one of the answers to the question you linked says that CPLEX automatically converts SOS1 constraints to binaries (which may be correct). You can, however, add a branch callback. In the branch callback, you might test whether both $X$ variables are positive. If so, you can branch with one of them set to zero in each child. If not, you can just let CPLEX branch as it normally would. So in addition to support for SOS1 branching, you might look for support for user-controlled branching. $\endgroup$ – prubin Nov 28 '20 at 18:23

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.