Tuesday, December 15, 2020

Modeling a simple implication

From [1]:

How to model:  

if \(\color{darkred}\delta=0\) then \(\color{darkred}x=0\) else \(\color{darkred}x=\color{darkred}x\)

where \(\color{darkred}\delta\in \{0,1\}\) is a binary variable and \(\color{darkred}x\ge 0\) is a non-negative continuous variable. 

The else part looks strange, but it is meant to indicate: unrestricted. So better is to just drop the else part:

if \(\color{darkred}\delta=0\) then \(\color{darkred}x=0\)

Let's list some possible formulations. 

Indicator constraint\[\color{darkred}\delta=0 \Rightarrow \color{darkred}x=0\]This is very natural. Assumes the solver (and modeling tool) supports indicator constraints. This means limiting the choice to high-end commercial solvers. Note that indicator constraints want to have a binary variable on the left. We were lucky here: that is exactly our situation. The solver will likely reformulate this under the hood (depending on the availability of bounds, one of the next two more basic formulations are target candidates). 
Big-M constraint\[\color{darkred}x\le \color{darkblue}M\cdot\color{darkred}\delta\]\(\color{darkblue}M\) is a tight upper bound on \(\color{darkred}x\). This can be implemented with any MIP solver. Disadvantage: we need to know a good upper bound on \(\color{darkred}x\). Large \(\color{darkblue}M\)s are dangerous. Anything above 1e6 is bad, but sometimes even smaller values give problems. If you have a good bound, this approach is often very efficient: solvers just like this formulation.
SOS1 constraint\[\begin{align}&\color{darkred}\eta=1-\color{darkred}\delta\\ & \{\color{darkred}\eta,\color{darkred}x\} \in \mathit{SOS1}\end{align}\]This formulation requires that the solver (and modeling tool) supports Special Ordered Sets of Type 1. We say here: \(\color{darkred}\eta\) is non-zero or \(\color{darkred}x\) is non-zero, but not both. Both can be zero however. Advantage: no bound needed. The auxiliary variable \(\color{darkred}\eta\) can be free, non-negative or binary.
Quadratic constraint\[(1-\color{darkred}\delta)\cdot\color{darkred}x=0 \]This is a non-convex constraint. Just a few solvers support this kind of constraint. Many types of "if-then", "or" and other conditions can be modeled quite naturally using quadratic terms. If more solvers start to provide support for this and the performance gets better, this may be a good way to model things. A good solver could reformulate this into something linear.

Even a simple construct like this can be formulated in different ways. This makes it a somewhat more interesting question than I initially thought.


No comments:

Post a Comment