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

[Brady Hunsaker]

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