Dantzig-Wolfe vs Benders Decomposition on the dual problem - Computational differences

Question

My question is a follow-up to this one: Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition. Here what is being discussed is the relationship between the two methods, and it is commented that while theoretically equivalent, there may be some computational differences. I want to learn about these computational differences. When does it make sense to switch to the dual in these circumstances?

Answer 1

A terminology note: Dantzig-Wolfe (DW) and Benders (BD) decomposition are formulations, not algorithms. DW decomposition is usually solved via column generation because, in general, it yields exponentially many variables. BD is usually solved via cutting plane because, similarly, it yields an exponential number of constraints.

TLDR: if you work with continuous problems, it probably doesn't matter too much, but if you have a mixed-integer problem, the choice will likely be imposed on you.

---

If you start from a linear program (P) then, as you know, DW decomposition on the primal is equivalent to Benders decomposition on the dual. Both approaches have identical sub-problems. Assuming the same sequence of sub-problem solves, the master problem in BD decomposition is the dual of the master problem in DW decomposition. As outlined by Marco Lübbecke in his answer to the original question, computational differences can arise if, e.g., the sequence of iterates is not the same. While most mainstream solvers will automatically dualize a problem if they deem it preferable, solving one or the other may give you a different solution and, in the end, different performance. Furthermore, although equivalent, there are, e.g., stabilization techniques, that can be more easily formulated in the dual problem than the primal. For instance, it's easier to add a box constraint on your dual multipliers if you're working with the dual (the primal would require artificial slack variables), or a quadratic proximal regularization.

That being said, DW and BD decomposition are not always applied to pure LP problems. In many practical settings, they arise from mixed-integer problems. In that case, you may not have the luxury of switching to the dual.

• One very desirable trait of BD decomposition is that you can implement it easily on top of a MIP solver, especially if it supports adding constraints via callbacks. It would be a lot harder to work on a DW formulation, because you wouldn't be able to use the solver's cuts, heuristics, branching, etc...
• If you have integer variables in your subproblem, then BD won't directly apply, because it normally relies on dual variables from the subproblem (you can get around that, but it's not trivial). When that happens, DW is your friend.