sci.op-research

Peter wrote:
>>> Peter
>> The objective function is the same in both problems? Are the variables
>> the same in both problems (which would not make much sense)? I can only
>> make sense of this if the variables in the outer problem parameterize
>> the constraints of the inner problem, but that would mean the inner
>> problem has different decision variables and likely a different
>> objective. Perhaps you could supply a small scale specific example.
>>
>> /Paul- Hide quoted text -
>>
>> - Show quoted text -
>
> A sample problem can be as following:
>
>
> (P)
> Min z1=x
> X <= y
>
> (P')
> Min z2=0
> y <= b (b is a constant)
> z1_min <= k (k is a constant)
>
> where z1_min, is the optimal value of the objective function for the
> problem (P). The decision variables in the problem (P') parameterize
> the constraints in the problem (P).

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