# Convert NL equality constraint involving minimum to linear inequality constraint?

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 $$x_1 =\min(x_2,\,x_3)\;.$$ I would like to convert it to a standard linear inequality constraint. My naive attempt was $$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)$$ Then, $$x_1 \leq \min(x_2,\,x_3) \to x_1 \leq x_2 \land x_1 \leq x_3\;.$$ But I am stuck with $$x_1 \geq \min(x_2,\,x_3)\;,$$ which I don't know how to linearize.

• Erwin's answer is correct for any objective function. If the nature of your problem is such that larger values of $x_1$ are always better (all other variables fixed), you can omit the lower limit on $x_1$ (and thus avoid turning the problem into an integer program). Dec 14 '17 at 20:18

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.
• direct implementation of $z=\min(x,y)$ using general constraints