# Modeling the product of two variables

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?

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

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.

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.

• 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? Nov 26, 2020 at 7:51
• 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.
– prubin
Nov 26, 2020 at 17:01
• Now with reference to this link or.stackexchange.com/questions/3104/… the question of which solver supports SOS1 branching arises. Nov 27, 2020 at 16:42
• 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.
– prubin
Nov 28, 2020 at 18:23