Recovering Dantzig–Wolfe Bounds by Cutting Planes

Dantzig–Wolfe (DW) decomposition is a well-known technique in mixed-integer programming (MIP) for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate cutting planes that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. More precisely, we generate one cut for each DW block, and when combined with the constraints in the original formulation, these cuts imply the objective function cut one can simply write using the DW bound. This approach typically leads to a formulation with lower dual degeneracy that consequently has a better computational performance when solved by standard MIP solvers in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. We test our approach on the multiple knapsack assignment problem and the temporal knapsack problem, and we show that the proposed cuts are helpful in accelerating the solution time without the need to implement branch and price.

Funding: This work was supported by the Office of Naval Research [Grant N00014-21-1-2575].

Supplemental Material: The e-companion is available at https://doi.org/10.1287/opre.2023.0048.