5
$\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
  • 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, 2017 at 20:18

1 Answer 1

Reset to default
5
$\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$
1
  • $\begingroup$ thank you for your answer. Would you please recommend some books or maybe links for linearization techniques ? $\endgroup$
    – Ibrahim Amer
    May 25, 2021 at 17:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .