3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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). $\endgroup$ – prubin Dec 14 '17 at 20:18
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.