Loading [MathJax]/jax/output/CommonHTML/jax.js

Tuesday, December 15, 2020

Modeling a simple implication

From [1]:

How to model:  

if δ=0 then x=0 else x=x

where δ{0,1} is a binary variable and x0 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 δ=0 then x=0


Let's list some possible formulations. 


formulationnotes
Indicator constraintδ=0x=0This 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 constraintxMδM is a tight upper bound on x. This can be implemented with any MIP solver. Disadvantage: we need to know a good upper bound on x. Large Ms 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η=1δ{η,x}SOS1This formulation requires that the solver (and modeling tool) supports Special Ordered Sets of Type 1. We say here: η is non-zero or x is non-zero, but not both. Both can be zero however. Advantage: no bound needed. The auxiliary variable η can be free, non-negative or binary.
Quadratic constraint(1δ)x=0This 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.


References



No comments:

Post a Comment