Tuesday, July 12, 2022

Linearize min(a,b)>min(x,y)

This question was posed [1]: How to linearize \[\min(\color{darkred}a,\color{darkred}b)\gt \min(\color{darkred}x,\color{darkred}y)\] where \(\color{darkred}a,\color{darkred}b,\color{darkred}x,\color{darkred}y\) are variables. The type of variables is not specified so let's assume they all are continuous variables.

The easiest is to split the problem in two parts: \[\begin{align} &\color{darkred}z = \min(\color{darkred}x,\color{darkred}y) \\ & \min(\color{darkred}a,\color{darkred}b) \gt \color{darkred}z\end{align}\] The first part: \(\color{darkred}z = \min(\color{darkred}x,\color{darkred}y)\) can be modeled with an extra binary variable \(\delta\): \[\begin{align}&\color{darkred}z \le \color{darkred}x \\ & \color{darkred}z \le \color{darkred}y \\ & \color{darkred}z \ge \color{darkred}x - \color{darkblue}M\cdot \color{darkred}\delta \\ & \color{darkred}z \ge \color{darkred}y - \color{darkblue}M\cdot (1-\color{darkred}\delta)\end{align}\] The constant \(\color{darkblue}M\) is a large enough number (but not larger) that should be chosen with care. This construct is essentially: \[\begin{align} & \color{darkred}z\le \color{darkred}x\> {\bf and }\> \color{darkred}z \le \color{darkred}y\\ & \color{darkred}z \ge \color{darkred}x \>{\bf or }\> \color{darkred}z \ge \color{darkred}y \end{align}\] 

If we cannot establish a good value for \(\color{darkblue}M\), we can use some alternatives for \[\begin{align}&\color{darkred}z \ge \color{darkred}x - \color{darkblue}M\cdot \color{darkred}\delta \\ & \color{darkred}z \ge \color{darkred}y - \color{darkblue}M\cdot (1-\color{darkred}\delta)\end{align}\] depending on what your MIP solver supports:

  • Indicator constraints: \[\begin{align}& \color{darkred}\delta=0 \implies \color{darkred}z \ge \color{darkred}x\\ & \color{darkred}\delta=1 \implies \color{darkred}z \ge \color{darkred}y\end{align}\]
  • SOS1 variables:  \[\begin{align}& \color{darkred}z \ge \color{darkred}x - \color{darkred}s_1\\ &  \color{darkred}z \ge \color{darkred}y -\color{darkred}s_2\\ & \color{darkred}s_1,\color{darkred}s_2 \ge 0 \\ &\color{darkred}s_1,\color{darkred}s_2 \in SOS1\end{align}\]



The remaining part \( \min(\color{darkred}a,\color{darkred}b) \gt \color{darkred}z\) can be modeled as: \[\color{darkred}a \gt \color{darkred}z\> {\bf and}\> \color{darkred}b \gt \color{darkred}z\] Putting things together, we have \[\begin{align}&\color{darkred}z \le \color{darkred}x \\ & \color{darkred}z \le \color{darkred}y \\ & \color{darkred}z \ge \color{darkred}x - \color{darkblue}M\cdot \color{darkred}\delta \\ & \color{darkred}z \ge \color{darkred}y - \color{darkblue}M\cdot (1-\color{darkred}\delta) \\ & \color{darkred}a \ge \color{darkred}z + 0.0001 \\& \color{darkred}b \ge \color{darkred}z + 0.0001\\ & \color{darkred}\delta \in \{0,1\}\end{align}\]

If we want, we can drop \(\color{darkred}z \le \color{darkred}x\) and \(\color{darkred}z \le \color{darkred}y\), as it is not a problem if \(\color{darkred}z\) becomes larger. This will make the value of \(\color{darkred}z\) a bit more difficult to interpret as it can float around a bit. Keeping these inequalities, maintains the interpretation: \(\color{darkred}z = \min(\color{darkred}x,\color{darkred}y)\).

Wanting to implement a \(\gt\) inequality for continuous variables is usually a mistake [2]. First: optimization models just don't work with \(\gt\). But also from a modeling point of view, I don't think I ever used this in a real model. For integer variables, \(\color{darkred}a\gt \color{darkred}z\) can be viewed better as \(\color{darkred}a \ge \color{darkred}z+1\). For continuous variables, you probably should not even consider \(\gt\). In this example, I just simulated \(\gt\) by a small constant.


References

 

2 comments:

  1. Great article! Mathematical nitpicking below…

    1. The sentence “Strict inequalities cause the feasible region to be an open set” is not mathematically correct. If all constraints are strict inequalities, then it is correct.

    2. The sentence “Mathematically, a maximum or minimum over an open set does not exist” is false.

    There are an infinite number of counter-examples to this sentence.

    I think you may have been trying to say the following: the existence of a maximum or minimum of a continuous (or smooth) function on an open set cannot be guaranteed without putting further conditions on the function. However, this existence is guaranteed for continuous (or smooth) functions over a compact set without any further conditions.

    Anyhow, apologies for the nitpicking. As a mathematician learning OR, your page is gold!

    Etienne AS

    ReplyDelete
    Replies
    1. My comment was aimed at reference 2: Strict Inequalities in Optimization Models.

      Delete