# How to linearize a min equality?

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)$$?

• 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. – John Omielan Feb 11 '19 at 17:51

If $$a$$ and $$b$$ are both constants, then there are two cases. If $$a, 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.