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

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

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

• Thanks. Do the following set of constraints work as well? $X \leq x_1 \\ X \leq x_2 \\ X \geq x_1 -Mz \\ X \geq x_2 -M(1-z) \\ x_1 \leq x_2 +Mz$ In this way, the first 4 constraints entitle X to be the min(x1,x2). Also, for x1>x2, z =1 and for x1<x2, z=0. Moreover, the last constraint forces y to be zero for x1=x2 as well (Not free anymore). Indeed, z is one's complement of the y in the original question. In my problem, x2 is constant and all variables X,x1, are non-negative. I am not sure if it does anything to do with it. @robpratt
– SAH
Sep 11, 2020 at 7:23
• No, $X=x_1=x_2$ is feasible for either value of $z$. Sep 11, 2020 at 13:04

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

• Thanks for your answer. However, I am interested in the general linearization of min operator while making sure that the auxiliary binary variable stays 1 for x1<=x2 @alex-fleischer
– SAH
Sep 10, 2020 at 13:22

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