sci.op-research

Peter wrote:
>> Neglecting for the moment the fact that, as written, (P) is unbounded, I
>> think I see (in general terms) where you are headed. I believe the
>> approach to take is to convert the condition z1_min <= k into a
>> constraint on y and fold that into (P'). If (P) is a linear program,
>> you can use duality.
>>
>> Let me write the problems in a somewhat more canonical form:
>>
>> (P) z(y) = min {d'x | Dx >= e + Hy}
>> (P') min {c'y | Ay >= b, z(y) >= k}
>>
>> where x and y are variables, z is a function and everything else is
>> parameters. We can use duality to get
>>
>> z(y) = max {u'e + u'Hy | u'D <= d', u >= 0}.
>>
>> For any given y, z(y) >= k iff there exists u >= 0 such that u'D <= d'
>> and u'e + u'Hy >= k. So rewrite (P') as
>>
>> min {c'y | Ay >= b, u'D <= d', u >= 0, u'e + u'Hy >= k}
>>
>> which, regrettably, is no longer a linear program due to the bilinear
>> final constraint.
>>
>> If you want a computational approach (as opposed to a nice (?)
>> formulation), I would suggest a cutting plane approach. Note that (a)
>> the constraints of the dual of (P) do not change when y changes, so that
>> the dual has the same feasible region for all y and (b) the objective
>> value of (P) for any given y is the minimum of u'e + u'Hy taken across
>> all vertices u of the dual feasible region. So z(y) >= k iff u'e + u'Hy
>> >= k for all vertices u of the dual region.
>>
>> So start with the LP
>>
>> min {c'y | Ay >= b}
>>
>> and solve it, getting y*. Now solve the dual of (P) with y = y*,
>> getting a vertex u* of the dual feasible region. If z(y*) >= k, you are
>> done. Otherwise, add the constraint u*'e + u*'Hy >= k to (P') and solve
>> again (say, with dual simplex). Iterate until you get a solution with
>> z(y*) >= k, which will happen in finitely many iterations since the dual
>> region has finitely many vertices.
>>
>> /Paul- Hide quoted text -
>>
>> - Show quoted text -
>
> Thanks ! It was very helpful.
> Actually, the reason why I couldn't write the sample problem in a form
> that makes sense, was that I was really confused with how I can
> mathematically express what was in my mind. Fortunately, you correctly
> got what I was looking for.
> Peter

So it looks like you are trying to solve bilevel problems.

You can find some discussion and experimental code here
http://control.ee.ethz.ch/~joloef/wiki/pmwiki.php?n=Examples.Bilevel

If you want to try it out, don't hesitate to contact me.
/johan