Hi,
I was reading about bender's decompostion method, had some doubts but
none of the links I got while googling cleared my doubts. Hope that
some one can explain in detail (if possible) the following :
What is the reason behind adding cuts to the master problem?
-I do understand that it will help in reducing the solution space to
search but my question is directed to the origin of the constraint(how
did we get such a constraint?).
What role do the extreme points and extreme directions play ?
Is there a problem (pref simple - hav come across many complicated
ones) where bender's method has been used ? - any pointers to
numerical examples ?
Any pointers to good and comprehensive explanation of the Bender's
Decomposition ?
TIA,
Darth

Have a look at : http://illposed.usc.edu/~fordon/LP03/lect19.pdf

can some one explain what the constrains mean (may be geometrically if
possible) on Page 3 ?

TIA,
Darth
Darth wrote:
Hi,

I was reading about bender's decompostion method, had some doubts but
none of the links I got while googling cleared my doubts. Hope that
some one can explain in detail (if possible) the following :

What is the reason behind adding cuts to the master problem?
-I do understand that it will help in reducing the solution space to
search but my question is directed to the origin of the constraint(how
did we get such a constraint?).

What role do the extreme points and extreme directions play ?

Is there a problem (pref simple - hav come across many complicated
ones) where bender's method has been used ? - any pointers to
numerical examples ?

Any pointers to good and comprehensive explanation of the Bender's
Decomposition ?
--
TIA,
Darth

Darth wrote:
Have a look at : http://illposed.usc.edu/~fordon/LP03/lect19.pdf

can some one explain what the constrains mean (may be geometrically if
possible) on Page 3 ?

enough, when I downloaded this file the key equations were missing
(?!). For instance, on page 3, " cut: If then " is
followed by empty space, then the next bullet. (It's particularly odd
since the document was generated by LaTeX, and I have MikTeX and a
pretty full set of fonts installed.) So I'm limited to giving a rather
generic explanation, based on what I can see (the master and slave
problems at the bottom of page 2). I'll preface this by mentioning
that, in general, there is no need for f and D to be the same for each
slave problem (they could be indexed f_i and D_i).

The phi functions in the master problem objective are intended to
capture the objective contributions of the slave problems. They're
written as functions of x to emphasize that the slave problem optimal
values depend on x, but in practice you would use variables, not
functions, in the master. So replace \phi_i(x) with z_i in the master,
where z_i is a new (continuous) variable for each i \in {1,,k}. If f
>= 0 (so that you know the objective contribution of the slave problem
is nonnegative), constrain z_i >= 0. To avoid having to deal with an
unbounded master problem, I'll assume that either z_i >= 0 or you have
an a priori lower bound for each z_i (which implies the slave is bounded
when x takes its globally optimal value).

When you first solve the master problem, there are no limits (other than
lower bound) on the z_i, so each z_i will equal its lower bound (meaning
that it in all likelihood underestimates the actual contribution of the
corresponding slave problem given the "optimal" value of x). Now pass
the "optimal" x to each slave and solve it. of three things will
happen. The slave might be infeasible; it might have an optimal
solution where the objective value exceeds z_i (so z_i underestimated
the actual contribution of the slave); or you have an optimal solution
where the objective value matches z_i. Two things cannot happen.
First, z_i cannot overestimate the objective contribution, since there
is (and never will be) anything in the master to push it above the
correct value. Second, the slave cannot be unbounded, because (from
duality theory) if it is unbounded for one x, it is unbounded for all x.
(The argument, in brief, is that if the slave is unbounded for some x,
its dual is infeasible for that x; but since x is in the objective of
the dual, the dual is then infeasible for all x, so the slave has no
optimum for any x, contradicting the assumption of a lower bound when x
is globally optimal.)

If the slave has an optimal value that matches z_i, that's good. When
that happens for every slave simultaneously, you're done: the primal
solution for x plus the slave solutions for the y_i represent an optimum
in the original problem. If the slave has an optimal solution but z_i
underestimates it, you use the optimal shadow prices w_i for the slave
(the solution to the dual of the slave) to form a globally valid
inequality that says

z_i = \phi_i(x) >= w_i'd_i - w_i'B_i x.

Note that since w_i, d_i and B_i are given, this turns into a linear
inequality involving z_i and x. This *should* be the "optimality cut"
mentioned on p. 3 (assuming that \gamma is the objective value of the
slave solution -- that's part of what is missing in my copy of the file).

What if the slave is infeasible for that particular value of x? Then
its dual (a maximization problem) is unbounded. You "solve" the dual to
get a ray w_i along which the dual objective (d_i - B_i x)'w_i grows
without bound. Note that the recession direction w_i is a recession
direction for any x (since in the dual x does not affect the
constraints). For the slave to feasible for some other x, the dual
objective based on that new value of x cannot improve along the ray, so
the recession direction w_i cannot be a direction of increase for the
dual objective. In other words, you need

(d_i - B_i x)'w_i <= 0

for the slave to be feasible given x. That should be the "feasibility
cut" mentioned on p. 3 (which, again, is invisible in my copy).

So the process is to solve the master for x and the z_i, then plug x
into each slave and solve it. If a slave is infeasible, its dual
solution gives you a feasibility cut that you add to the master. (Note
that the feasibility cut involves x but not z_i, and that the current
value of x violates it.) If the slave has an optimal value greater than
z_i, the dual solution gives you an optimality cut involving x and z_i,
which you add to the master. Again, the current combination of x and
z_i violates that cut. If the slave has an optimal solution whose
objective value matches z_i, it contributes nothing. Add whatever cuts
you get to the master and reoptimize. When no slave coughs up a new
cut, you're done.

HTH,
/Paul

Hi Paul,

Thanks to you I have most of my doubts cleared. I really appreciate
your help.
Its not a Latex problem, I checked it on Linux, probably its purposely
left empty.

I have a couple of very basic questions to ask, kindly answer them
too.

Paul A. Rubin wrote:
Darth wrote:
Have a look at : http://illposed.usc.edu/~fordon/LP03/lect19.pdf

can some one explain what the constrains mean (may be geometrically if
possible) on Page 3 ?
--
enough, when I downloaded this file the key equations were missing
(?!). For instance, on page 3, " cut: If then " is
followed by empty space, then the next bullet. (It's particularly odd
since the document was generated by LaTeX, and I have MikTeX and a
pretty full set of fonts installed.) So I'm limited to giving a rather
generic explanation, based on what I can see (the master and slave
problems at the bottom of page 2). I'll preface this by mentioning
that, in general, there is no need for f and D to be the same for each
slave problem (they could be indexed f_i and D_i).

The phi functions in the master problem objective are intended to
capture the objective contributions of the slave problems. They're
written as functions of x to emphasize that the slave problem optimal
values depend on x, but in practice you would use variables, not
functions, in the master. So replace \phi_i(x) with z_i in the master,
where z_i is a new (continuous) variable for each i \in {1,,k}. If f
>= 0 (so that you know the objective contribution of the slave problem
is nonnegative), constrain z_i >= 0. To avoid having to deal with an
unbounded master problem, I'll assume that either z_i >= 0 or you have
an a priori lower bound for each z_i (which implies the slave is bounded
when x takes its globally optimal value).

When you first solve the master problem, there are no limits (other than
lower bound) on the z_i, so each z_i will equal its lower bound (meaning
that it in all likelihood underestimates the actual contribution of the
corresponding slave problem given the "optimal" value of x). Now pass
the "optimal" x to each slave and solve it. of three things will
happen. The slave might be infeasible; it might have an optimal
solution where the objective value exceeds z_i (so z_i underestimated
the actual contribution of the slave); or you have an optimal solution
where the objective value matches z_i. Two things cannot happen.
First, z_i cannot overestimate the objective contribution, since there
is (and never will be) anything in the master to push it above the
correct value. Second, the slave cannot be unbounded, because (from
duality theory) if it is unbounded for one x, it is unbounded for all x.
(The argument, in brief, is that if the slave is unbounded for some x,
its dual is infeasible for that x; but since x is in the objective of
the dual, the dual is then infeasible for all x, so the slave has no
optimum for any x, contradicting the assumption of a lower bound when x
is globally optimal.)

If the slave has an optimal value that matches z_i, that's good. When
that happens for every slave simultaneously, you're done: the primal
solution for x plus the slave solutions for the y_i represent an optimum
in the original problem. If the slave has an optimal solution but z_i
underestimates it, you use the optimal shadow prices w_i for the slave
(the solution to the dual of the slave) to form a globally valid
inequality that says

z_i = \phi_i(x) >= w_i'd_i - w_i'B_i x.

Note that since w_i, d_i and B_i are given, this turns into a linear
inequality involving z_i and x. This *should* be the "optimality cut"
mentioned on p. 3 (assuming that \gamma is the objective value of the
slave solution -- that's part of what is missing in my copy of the file).

What if the slave is infeasible for that particular value of x? Then
its dual (a maximization problem) is unbounded. You "solve" the dual to
get a ray w_i along which the dual objective (d_i - B_i x)'w_i grows
without bound. Note that the recession direction w_i is a recession
direction for any x (since in the dual x does not affect the
constraints). For the slave to feasible for some other x, the dual
objective based on that new value of x cannot improve along the ray, so
the recession direction w_i cannot be a direction of increase for the
dual objective. In other words, you need

(d_i - B_i x)'w_i <= 0

for the slave to be feasible given x. That should be the "feasibility
cut" mentioned on p. 3 (which, again, is invisible in my copy).

Could you explain the above a bit more in detail. Why do we need it to
be <= 0 ?
And why exactly cannot the dual objective for the new x improve along
the ray ?

Is it because, for any x the dual objective grows without bound along
this direction w_i so we want to eliminate the possibility of getting
w_i again?

So the process is to solve the master for x and the z_i, then plug x
into each slave and solve it. If a slave is infeasible, its dual
solution gives you a feasibility cut that you add to the master. (Note
that the feasibility cut involves x but not z_i, and that the current
value of x violates it.) If the slave has an optimal value greater than
z_i, the dual solution gives you an optimality cut involving x and z_i,
which you add to the master. Again, the current combination of x and
z_i violates that cut. If the slave has an optimal solution whose
objective value matches z_i, it contributes nothing. Add whatever cuts
you get to the master and reoptimize. When no slave coughs up a new
cut, you're done.

HTH,
/Paul

Darth wrote:

>What if the slave is infeasible for that particular value of x? Then
>its dual (a maximization problem) is unbounded. You "solve" the dual to
>get a ray w_i along which the dual objective (d_i - B_i x)'w_i grows
>without bound. Note that the recession direction w_i is a recession
>direction for any x (since in the dual x does not affect the
>constraints). For the slave to feasible for some other x, the dual
>objective based on that new value of x cannot improve along the ray, so
>the recession direction w_i cannot be a direction of increase for the
>dual objective. In other words, you need
>>
>(d_i - B_i x)'w_i <= 0
>>
>for the slave to be feasible given x. That should be the "feasibility
>cut" mentioned on p. 3 (which, again, is invisible in my copy).
>>
>
Could you explain the above a bit more in detail. Why do we need it to
be <= 0 ?
And why exactly cannot the dual objective for the new x improve along
the ray ?

Duality theory says that if the primal LP is infeasible, the dual LP is
either infeasible or unbounded. Since x occurs only in the objective of
the dual, if the dual is infeasible for any x, it is infeasible for all
x, which means the primal is either infeasible or unbounded for all x.
I'm charitably assuming here that the original problem has an optimal
solution, which means for the optimal x the primal slave LP has an
optimum, which means its dual is feasible for that x, and thus for every
x. <Pause to catch breath here.>

Suppose the master problem coughs up some x for which the slave is
infeasible. We've just established the dual of the slave is feasible
for the optimal x, and thus for all x, so the dual must be unbounded.
That means that there is a feasible dual solution q and a dual recession
direction w (a direction in which the dual feasible region extends
without bound, so that q+t*w is dual feasible for all t>=0), such that
the dual objective improves forever in that direction. Since you are
maximizing (d_i - B_i x)'s (s being the dual variable), improvement
along the ray means that (d_i - B_i x)'w 0.

again, the dual feasible region has nothing to do with x, so that
ray (q + t*w, t>=0) is going to be there for any x you propose. You
need an x for which the dual is bounded (else the primal is infeasible).
Since you're stuck with the ray, all you can do is require that the
dual objective not improve along the ray, which means (d_i - B_i x)'w <= 0.

Is it because, for any x the dual objective grows without bound along
this direction w_i so we want to eliminate the possibility of getting
w_i again?

Not exactly, but close. You don't care if the dual solution lies on the
ray; you care that the dual objective does not improve along the ray.

/Paul

Thanks,
Darth
Paul A. Rubin wrote:
Darth wrote:
>
>What if the slave is infeasible for that particular value of x? Then
>its dual (a maximization problem) is unbounded. You "solve" the dual to
>get a ray w_i along which the dual objective (d_i - B_i x)'w_i grows
>without bound. Note that the recession direction w_i is a recession
>direction for any x (since in the dual x does not affect the
>constraints). For the slave to feasible for some other x, the dual
>objective based on that new value of x cannot improve along the ray, so
>the recession direction w_i cannot be a direction of increase for the
>dual objective. In other words, you need
>>
>(d_i - B_i x)'w_i <= 0
>>
>for the slave to be feasible given x. That should be the "feasibility
>cut" mentioned on p. 3 (which, again, is invisible in my copy).
>>
>
Could you explain the above a bit more in detail. Why do we need it to
be <= 0 ?
And why exactly cannot the dual objective for the new x improve along
the ray ?

Duality theory says that if the primal LP is infeasible, the dual LP is
either infeasible or unbounded. Since x occurs only in the objective of
the dual, if the dual is infeasible for any x, it is infeasible for all
x, which means the primal is either infeasible or unbounded for all x.
I'm charitably assuming here that the original problem has an optimal
solution, which means for the optimal x the primal slave LP has an
optimum, which means its dual is feasible for that x, and thus for every
x. <Pause to catch breath here.>

Suppose the master problem coughs up some x for which the slave is
infeasible. We've just established the dual of the slave is feasible
for the optimal x, and thus for all x, so the dual must be unbounded.
That means that there is a feasible dual solution q and a dual recession
direction w (a direction in which the dual feasible region extends
without bound, so that q+t*w is dual feasible for all t>=0), such that
the dual objective improves forever in that direction. Since you are
maximizing (d_i - B_i x)'s (s being the dual variable), improvement
along the ray means that (d_i - B_i x)'w 0.

again, the dual feasible region has nothing to do with x, so that
ray (q + t*w, t>=0) is going to be there for any x you propose. You
need an x for which the dual is bounded (else the primal is infeasible).
Since you're stuck with the ray, all you can do is require that the
dual objective not improve along the ray, which means (d_i - B_i x)'w <= 0.

Is it because, for any x the dual objective grows without bound along
this direction w_i so we want to eliminate the possibility of getting
w_i again?

Not exactly, but close. You don't care if the dual solution lies on the
ray; you care that the dual objective does not improve along the ray.

/Paul