Wednesday, May 16, 2018

Indicator constraints

In [1] a question is posed about how to implement the implication:\[ x+y\le 5 \Rightarrow \delta = 1\] Here \(\delta \in \{0,1\}\) is a binary variable. Indicator constraints are of the form:\[ \delta = 0 \Rightarrow \text{constraint}\] or \[ \delta = 1 \Rightarrow \text{constraint}\] The binary variable \(\delta\) is sometimes called an indicator variable.

From propositional logic we have: \[\begin{align} & A \Rightarrow B \\ & \Leftrightarrow \\  & \neg B \Rightarrow \neg A\end{align}\] This is called transposition [2].

From this, we can formulate:\[\delta = 0 \Rightarrow x+y\gt 5\] If \(x\) or \(y\) is a continuous variable we can choose to write \[\delta = 0 \Rightarrow x+y\ge 5.001\] or just \[\delta = 0 \Rightarrow x+y\ge 5\] In the latter case we keep things ambiguous for \( x+y=5\) which is in practice often a good choice.

If  \(x\) and \(y\) are integers, we can do: \[\delta = 0 \Rightarrow x+y\ge 6\]

This trick is quite useful to know when dealing with indicator constraints.

References