Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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);
share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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)$ –  gnychis Apr 1 '12 at 19:22
    
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. –  gnychis Apr 1 '12 at 20:31
    
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? –  fabee Apr 2 '12 at 5:45
    
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! –  gnychis Apr 2 '12 at 14:18
    
You are welcome. I removed the part about the unboundedness to make it consistent with your post. –  fabee Apr 3 '12 at 6:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.