Weighted Dantzig–Wolfe decomposition for linear mixed-inter programming

Dantzig–Wolfe decomposition can be used to solve the Lagrangian dual of a linear mixed-integer programming problem MIP if the dual structure of the (MIP) is exploited via Lagrangian relaxation with respect to the complicating constraints. In the so-called weighted Dantzig–Wolfe decomposition algorithm, instead of the optimal solution of the Dantzig–Wolfe master problem a specially weighted average of the previously constructed Lagrangian multipliers and the optimal solution of the master problem is used as Lagrangian multiplier for the next Lagrangian subproblem to be solved. A convergence proof of the weighted Dantzig–Wolfe decomposition algorithm is given, and some properties of this procedure together with computational results for the capacitated facility location problem are discussed.