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

2 Answers 2

Reset to default
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$
4
  • $\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, 2020 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, 2020 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, 2020 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, 2020 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.