Convert NL equality constraint involving minimum to linear inequality constraint?

Question

Is it possible to convert an equality constraint involving the minimum, to a linear inequality constraint?

Suppose I have an optimization problem which involves the variables $x_1,\,x_2,\,x_3$, with the constraint \begin{equation} x_1 =\min(x_2,\,x_3)\;. \end{equation} I would like to convert it to a standard linear inequality constraint. My naive attempt was \begin{equation} x_1 =\min(x_2,\,x_3) \to x_1 \leq \min(x_2,\,x_3)\, \land\, x_1 \geq \min(x_2,\,x_3) \end{equation} Then, \begin{equation} x_1 \leq \min(x_2,\,x_3) \to x_1 \leq x_2 \land x_1 \leq x_3\;. \end{equation} But I am stuck with \begin{equation} x_1 \geq \min(x_2,\,x_3)\;, \end{equation} which I don't know how to linearize.

Answer 1

The constraint $$ z = \min(x,y) $$ can be interpreted as: $$ \begin{align} &z \le x \text{ and } z \le y\\ &z \ge x \text{ or } z \ge y \end{align} $$ This can be implemented in a MIP model using a big-$M$ formulation: $$ \begin{align} &z \le x\\ &z \le y\\ &z \ge x - M\delta\\ &z \ge y - M(1-\delta)\\ &\delta \in \{0,1\} \end{align} $$ where $M$ is a large enough constant.

Advanced solvers have capabilities that can provide alternative approaches, such as

• SOS1 variables
• indicator constraints
• direct implementation of $z=\min(x,y)$ using general constraints