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

3

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
    Thanks so much, this worked out great for me! Just a comment though, when you do that substitution with the variables, I believe the sign is distributed so that this is the final: $min(x,y) = \frac{1}{2} (x + y - z_1 - z_2)$2012-04-01
  • 0
    Also, it seems as though if this is in the objective function and the function is to maximize the value, it will take on min(x,y). However, if the objective function is to minimize, it will take on the value of 0. I want it to always take on the min, however.2012-04-01
  • 0
    Sure, the sign is distributed (sorry for being unclear about that). Concerning your second comment, I do not see how that can happen. The constraint $z_1-z_2 = x-y$ should ensure that $z_1$ and $z_2$ cannot cancel $x$ and $y$ (because then $z_1 + z_2 = -(x+y) \not= x-y$. Or am I missing something?2012-04-02
  • 0
    I added in the output of minimizing in the objective function, where it shows that my value will go to 0. Check out my main post again. Thanks for your help!2012-04-02
  • 0
    You are welcome. I removed the part about the unboundedness to make it consistent with your post.2012-04-03
  • 0
    Great! Sorry for the constant typo in your username, it's Apple's autocorrect at work. Fixed.2012-04-03
  • 0
    :) I already wondered what's the reason for it. Don't worry.2012-04-04