3
$\begingroup$

I am trying to formulate an LP problem. In the problem I have a $\min(X,Y)$ that I would like to formulate linearly as a set of constraints. For example, replacing $\min(X,Y)$ with some variable $Z$, and having a set of constraints on Z.

I believe that there are a minimum of two constraints:

subto: $Z \le X$
subto: $Z \le Y$

That will make it take a value that is less than or equal to $\min(X,Y)$. But, I want it to take the minimum value of $X$ or $Y$. I am missing one constraint, that seems to have the following logic: "$Z \ge X$ or $Z \ge Y$" ... so that it isn't just less than the minimum, it IS the minimum. I know I'm missing something basic.


In addition to fabee's response, I also have found this representation to work well which uses either-or constraint representation. Note that M must be large, see 15.1.2.1 in this document.

param a := 0.8; param b := 0.4; param M := 100; var z; var y binary;  minimize goal: z;  subto min_za:   z <= a;  subto min_zb:   z <= b;  subto min_c1:   -z <= -a + M*y;  subto min_c2:   -z <= -b + M*(1-y); 

1 Answers 1

4

You could use $\min(x,y) = \frac{1}{2}(x + y - |x - y|)$ where $|x - y|$ can be replaced by the variables $z_1 + z_2$ with constraints $z_i \ge 0$ for $i=1,2$ and $z_1 - z_2 = x - y$. $z_1$ and $z_2$ are, therefore, the positive or the negative part of $|x-y|$.

Edit:

For the reformulation to work, you must ensure that either $z_1=0$ or $z_2=0$ at the optimum, because we want $z_1 = \begin{cases} x-y & \mbox{ if }x-y\ge0\\ 0 & \mbox{ otherwise} \end{cases}$ and $z_2 = \begin{cases} y-x & \mbox{ if }x-y\le0\\ 0 & \mbox{ otherwise} \end{cases}.$

You can check that the constraints will be active if the objective function can always be increase/decreased by making one of the $z_i$ smaller. That is the reason why your maximization worked, because the objective function could be increased by making one of the $z_i$ smaller.

You could fix your minimization example by requiring that $0\le z_i \le |x-y|$. In that case, the objective function will be smallest if $z_i$ are largest. However, since they still need to be $3$ apart, one of the $z_i$ will be three and the other one will be zero.

  • 0
    :) I already wondered what's the reason for $i$t. Don't worry.2012-04-04