How to linearize the Min function while letting the binary variable to be fixed for x1==x2 as well?

Question

As discussed here, the min function, i.e $X = \min\{x_1,x_2\}$, can be linearized as follows:

\begin{align} X & \le x_1 \\ X & \le x_2 \\ X & \ge x_1 - M(1-y) \\ X & \ge x_2 - My. \end{align} In this way, when $x_1<x_2$ then the binary variable $y$ is equal to $1$. However, when $x_1>x_2$ then $y=0$. Nevertheless, for $x_1==x_2$, the binary variable y can either take $0$ or $1$ (free). How can I force $y$ also to be equal to $1$ for $x_1==x_2$ in the above linearization?

Answer 1

Consider the contrapositive $y=0 \implies x_1 \not= x_2$, equivalently, $y=0 \implies (x_1 < x_2 \lor x_1 > x_2)$. Introduce a small constant tolerance $\epsilon>0$, two additional binary variables $z_1$ and $z_2$, and the following constraints: \begin{align} 1 - y &\le z_1 + z_2 \tag1 \\ x_1 +\epsilon - x_2 &\le M(1-z_1) \tag2 \\ x_2 +\epsilon - x_1 &\le M(1-z_2) \tag3 \end{align} Constraint $(1)$ enforces $\neg y \implies (z_1 \lor z_2)$. Constraint $(2)$ enforces $z_1 \implies x_1 + \epsilon \le x_2$. Constraint $(3)$ enforces $z_2 \implies x_2 + \epsilon \le x_1$.

Answer 2

side comment : in many tools you can use min directly and then you do not need to linearize.

In OPL CPLEX

dvar int x in 0..10;
dvar int y in 0..10;
dvar int z in 0..10;

maximize (x-y);
subject to
{
  z==minl(x,y);
}

works fine

And

dvar int x in 0..10;
dvar int y in 0..10;
dvar int z in 0..10;

dvar boolean xlessthany;


subject to
{
  x==y;
  z==minl(x,y);
  xlessthany==(x<=y);
}

if you want a boolean decision variable to know whether x is less than y

Answer 3

Once we have remembered that $\min f(x)=-\max (-f(x))$, we wish Boolean variable $y$ is forced to $1$ whenever $y$ is free to be $1$ or $0$, so we can add $-y$ to the objective function $Z=-q_1p_1$, so that $Z’=-q_1p_1-y$.

In this way, $\min Z’$ forces $y$ to be equal to $1$ when $x_1=x_2$ because of $$\min Z’=\min(-q_1p_1) + \min(-y)= \min Z - \max y.$$

In fact, $\max(y) \implies y=1$ whenever $y$ is free to be $1$ or $0$.