4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – SAH Sep 11 at 7:23
  • 1
    $\begingroup$ No, $X=x_1=x_2$ is feasible for either value of $z$. $\endgroup$ – RobPratt Sep 11 at 13:04
2
$\begingroup$

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

| improve this answer | |
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – SAH Sep 10 at 13:22
1
$\begingroup$

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

| improve this answer | |
$\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.