sci.op-research

On Mar 25, 11:52=A0pm, Paul Rubin wrote:
> Peter wrote:
> >>> Peter
> >> The objective function is the same in both problems? =A0Are the variabl=
es
> >> the same in both problems (which would not make much sense)? =A0I can o=
nly
> >> 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. =A0Perhaps 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=3Dx
> > X <=3D y
>
> > (P')
> > Min z2=3D0
> > y <=3D b =A0(b is a constant)
> > z1_min <=3D k =A0(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. =A0I believe the
> approach to take is to convert the condition z1_min <=3D k into a
> constraint on y and fold that into (P'). =A0If (P) is a linear program,
> you can use duality.
>
> Let me write the problems in a somewhat more canonical form:
>
> (P) z(y) =3D min {d'x | Dx >=3D e + Hy}
> (P') min {c'y | Ay >=3D b, z(y) >=3D k}
>
> where x and y are variables, z is a function and everything else is
> parameters. =A0We can use duality to get
>
> z(y) =3D max {u'e + u'Hy | u'D <=3D d', u >=3D 0}.
>
> For any given y, z(y) >=3D k iff there exists u >=3D 0 such that u'D <=3D =
d'
> and u'e + u'Hy >=3D k. =A0So rewrite (P') as
>
> min {c'y | Ay >=3D b, u'D <=3D d', u >=3D 0, u'e + u'Hy >=3D 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. =A0Note 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. =A0So z(y) >=3D k iff u'e + u'=
Hy
> =A0>=3D k for all vertices u of the dual region.
>
> So start with the LP
>
> min {c'y | Ay >=3D b}
>
> and solve it, getting y*. =A0Now solve the dual of (P) with y =3D y*,
> getting a vertex u* of the dual feasible region. =A0If z(y*) >=3D k, you a=
re
> done. =A0Otherwise, add the constraint u*'e + u*'Hy >=3D k to (P') and sol=
ve
> again (say, with dual simplex). =A0Iterate until you get a solution with
> z(y*) >=3D k, which will happen in finitely many iterations since the dual=

> region has finitely many vertices.
>
> /Paul- Hide quoted text -
>
> - Show quoted text -

As you said we have the following problems:

(P) z(y) =3D min {d'x | Dx >=3D e + Hy}
(P') min {c'y | Ay >=3D b, z(y) >=3D k}
Dual: z(y) =3D max {u'e + u'Hy | u'D <=3D d', u >=3D 0}.
min {c'y | Ay >=3D b, u'D <=3D d', u >=3D 0, u'e + u'Hy >=3D k}

So, we have a nonlinear term u'e + u'Hy in the dual problem and in
the constraint
u'e + u'Hy >=3D k. If the variable y turns out to be binary, is there
any way to get rid of it in the dual problem and in that constraint
(with respect to the fact that y can take a value of only 0 or 1) so
that have a linear problem?

Peter