How to linearize a min equality?

Question

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

Answer 1

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.

---