It’s often said that “Benders decomposition is Dantzig-Wolfe applied to the dual”. How can this statement be made precise? I know that in Dantzig-Wolfe, cuts are added in one-to-one correspondence with the extreme points of the primal feasible region—is Benders like this but for dual extreme points? I’m interested in explanations highlighting the parallels between the two methods.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
My experience is that even when two methods "are equivalent" (eg in the sense that they give the same dual bound), and even though they may be technically "the same" (like "Benders is DW applied to the dual"), such methods may significantly differ when looking at the computational side. DW and Lagrangian relaxation also give the same dual bound, and (dual) multipliers from one can be easily interpreted in the other, but still, in computations, the sequence of these multipliers, thus, the sequence of solutions, can be very different.
Just keep that in mind when you read "is the same as ..., but applied to the dual."
$\begingroup$
$\endgroup$
"Benders’ decomposition is Dantzig-Wolfe decomposition applied to the dual" is the first sentence of Section 10.3 in Dantzig & Thapa's Linear programming 2: theory and extensions, which then proceeds to give a precise statement of this correspondence.
$\begingroup$
$\endgroup$
If a linear programming problem has a decomposable structure with complicating constraints, its dual linear programming problem has a decomposable structure with complicating variables. And conversely, if a linear programming problem has a decomposable structure with complicating variables, its dual linear programming problem has a decomposable structure with complicating constraints.
A problem with complicating variables can be transformed, using the dual problem, into a problem with complicating constraints.
$\begingroup$
$\endgroup$
In theoretical side, two methods are indeed the same. I suggest to read "Relationship with Dantzig-Wolfe Decomposition" section of this post as a simple proof.
The way show the equivalence in the above post is to apply DW decomposition on the dual problem and take dual again. Then, it is easy to see that DW formulation for dual problem is same as the Bender's decomposition formulation for primal problem.
In computational side, as Marco's answer said, two methods still have different performance in their performances.
