2
$\begingroup$

I have a linear program that has a constraint as follows :

$$a = \min\{b,x\},$$

where $x$ is the variable.

I tried to write it as $$a\leq\min\{b,x\}\tag{1},$$

and

$$a\geq\min\{b,x\}.\tag{2}$$

Equation $(1)$ is equivalent to the two inequalities :

$$a\leq b,$$ and $$a\leq x.$$

How to deal with equation $(2)$?

$\endgroup$
  • $\begingroup$ How to linearize max, min, and abs functions, posted by Prof. Leandro C. Coelho, Ph.D., the Canada Research Chair in Integrated Logistics, provides a method for the general min function. Erwin Kalvelagen stated in a comment to an answer I've deleted that it should be non-convex, that usually a general OR condition ($x \ge a$ or $x \ge b$) is modeled with binary variables, and he suspects penalyzing the $S^+, S^−$ (mentioned in the method) will change the solution. $\endgroup$ – John Omielan Feb 11 '19 at 17:51
0
$\begingroup$

If $a$ and $b$ are both constants, then there are two cases. If $a<b$, then the constraint can be written as $x=a$. If $a=b$, then the constraint can be written as $x\geq b$. If $a>b$, then the constraint is violated.


If $a$ is a variable, there are also two cases.

  1. The first is that $a$ has a negative coefficient in the linear minimization objective (or a positive coefficient in the maximization objective). If that's the case, then it will actually just suffice to put what you've put: $a\leq b$, and $a\leq x$. The reason is that decreasing $a$ below the minimum (violating inequality) would incur a detrimental cost in the objective.
  2. The second is that $a$ has non-negative coefficient in the minimization objective. If that's the case, then the constraint cannot necessarily be enforced, since the problem may not be convex. For instance, the simple problem $$\begin{align*} \min_{x,a}\quad& a\\ \text{s.t.}\quad& a=\min\{1,x\}\\ &x,a\geq 0 \end{align*}$$ is non-convex since $(x,a)=(0,0)$ is feasible, and $(x,a)=(2,1)$ is feasible, but a convex combination of these $(x,a)=(1,\frac{1}{2})$ is not feasible. Linear programmes must have convex feasible regions.

If $a$ is a constant and $b$ is a variable, then again, the problem mightn't be convex, so once again you can't necessarily write a linear constraint which is equivalent. For example, $$\begin{align*} \min_{x,b}\quad& x+b\\ \text{s.t.}\quad& 1=\min\{b,x\} \end{align*}$$ is not convex, since $(1,3)$ and $(3,1)$ are both feasible but the convex combination $(2,2)$ is not.


In all cases, you can turn your linear programme into a mixed-integer linear programme by defining a new variable $z\in\{0,1\}$ which equals $1$ when $a=b$ and equals $0$ when $a=x$. In particular, you can write the constraints as $$\begin{align*} a&\leq b\\ a&\leq x\\ a&\geq x-Mz\\ a&\geq b-M(1-z)\\ x&\leq b+Mz\\ b&\leq x+Mb\\ z&\in\{0,1\} \end{align*} $$ where $M$ is a big-M value.


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