Consistency Cuts for Dantzig-Wolfe Reformulations

Jens Vinther Clausen (), Richard Lusby () and Stefan Ropke ()
Additional contact information
Jens Vinther Clausen: Department of Technology, Management, and Economics, Technical University of Denmark, Kongens Lyngby DK-2800, Denmark
Richard Lusby: Department of Technology, Management, and Economics, Technical University of Denmark, Kongens Lyngby DK-2800, Denmark
Stefan Ropke: Department of Technology, Management, and Economics, Technical University of Denmark, Kongens Lyngby DK-2800, Denmark

Operations Research, 2022, vol. 70, issue 5, 2883-2905

Abstract: This paper introduces a family of valid inequalities, which we term consistency cuts, to be applied to a Dantzig-Wolfe reformulation (or decomposition) with linking variables. We prove that these cuts ensure an integer solution to the corresponding Dantzig-Wolfe relaxation when certain criteria to the structure of the decomposition are met. We implement the cuts and use them to solve a commonly used test set of 200 instances of the temporal knapsack problem. We assess the performance with and without the cuts and compare further to CPLEX and other solution methods that have historically been used to solve the test set. By separating consistency cuts, we show that we can obtain optimal integer solutions much faster than the other methods and even solve the remaining unsolved problems in the test set. We also perform a second test on instances from the MIPLIB 2017 online library of mixed-integer programs, showing the potential of the cuts on a wider range of problems.

Keywords: Optimization; integer programming; cutting plane/facet; algorithms; theory (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2160 (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:70:y:2022:i:5:p:2883-2905

Access Statistics for this article

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