[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