Recovering Dantzig–Wolfe Bounds by Cutting Planes

Rui Chen (), Oktay Günlük () and Andrea Lodi ()
Additional contact information
Rui Chen: Cornell Tech, New York, New York 10044
Oktay Günlük: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14850
Andrea Lodi: Jacobs Technion–Cornell Institute, Cornell Tech and Technion–Israel Institute of Technology, New York, New York 10044

Operations Research, 2025, vol. 73, issue 2, 1128-1142

Abstract: 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.

Keywords: Optimization; integer programming; Dantzig–Wolfe decomposition; cutting plane method (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0048 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:1128-1142

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().