[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## Re: [Help-glpk] help solve a lp problem, please

**From**: |
Brady Hunsaker |

**Subject**: |
Re: [Help-glpk] help solve a lp problem, please |

**Date**: |
05 Feb 2004 18:49:08 -0500 |

On Sun, 2004-02-01 at 01:24, George Cao wrote:
>* Hi everyone,*
>* *
>* For the lp gurus in the group, can you guys take a look at this problem *
>* and see if you can provide some pointers?*
>* *
>* maximize:*
>* r1* x1a + r2 * x1b + r2*x2 (note: r1, r2 are constants and r2 is *
>* always greater than r1)*
>* *
>* Subject to:*
>* x1a + x1b <= d1*
>* x2 <= d2*
>* 10 * x1b <= d1*
>* x1a <= c1*
>* x1b + x2 <= c2*
>* x1a, x1b, x2 >=0*
>* *
>* This works fine so far. But I need to add a couple more constraints:*
>* if (c1 - x1a - x1b) >= 0 let x1b = 0*
>* if (c1 - x1a - x1b) < 0 x1b can be any number >= 0*
>* *
>* I can't figure out how to incorporate these constraints into the lp *
>* problem. Adding (c1 - x1a - x1b) >= 1000000 * x1b works when (c1 - x1a *
>* - x1b) >= 0, but will make the whole problem not feasible when (c1 - x1a *
>* - x1b) < 0.*
>* *
>* Some help please?*
>* *
>* Thanks in advance.*
>* *
>* George*
>* *
As I understand it, what you would like is to have
x1b = 0 or x1b > c1- x1a
The strict inequality is likely to be a problem no matter what, but if
we change it slightly:
x1b = 0 or x1b >= c1 - x1a
Variables like this are often called semi-continuous variables, though
typically the lower bound on the right would be a constant. These are
handled using a binary variable, making your problem an IP.
Let Y be a binary variable. I think the following will work:
x1b >= 0
x1a >= 0
x1b >= c1 * Y - x1a
x1b <= [upper bound on x1b] * Y
Y in {0,1}
If Y=0, then you get x1b >= - x1a (feasible since x1a >= 0) and x1b <=
0, so x1b = 0.
If Y=1, then you get x1b >= c1 - x1a and x1b <= [upper bound on x1b].
It is in your best interest to have that [upper bound on x1b] be the
lowest bound possible. It looks like that is 0.1 * d1.
Note: remember that we did not do the strict inequality that you
wanted. If that really matters then this won't quite work.
Brady