Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows

Luciano Costa (), Claudio Contardo (), Guy Desaulniers () and Julian Yarkony ()
Additional contact information
Luciano Costa: Department of Production Engineering, Federal University of Pernambuco, Caruaru 55002-917, Brazil
Claudio Contardo: Department of Analytics, Operations, and Information Technologies, School of Business, University of Quebec in Montreal (ESG UQAM), Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, H3T 1J4, Canada
Guy Desaulniers: Department of Applied Mathematics and Industrial Engineering and Group for Research in Decision Analysis (GERAD), Montréal, H3T 2A7, Canada
Julian Yarkony: Laminaar, San Diego, California 92122

INFORMS Journal on Computing, 2022, vol. 34, issue 2, 1141-1156

Abstract: Column generation (CG) algorithms are well known to suffer from convergence issues due, mainly, to the degenerate structure of their master problem and the instability associated with the dual variables involved in the process. In the literature, several strategies have been proposed to overcome this issue. These techniques rely either on the modification of the standard CG algorithm or on some prior information about the set of dual optimal solutions. In this paper, we propose a new stabilization framework, which relies on the dynamic generation of aggregated rows from the CG master problem. To evaluate the performance of our method and its flexibility, we consider instances of three different problems, namely, vehicle routing with time windows (VRPTW), bin packing with conflicts (BPPC), and multiperson pose estimation (MPPEP). When solving the VRPTW, the proposed stabilized CG method yields significant improvements in terms of CPU time and number of iterations with respect to a standard CG algorithm. Huge reductions in CPU time are also achieved when solving the BPPC and the MPPEP. For the latter, our method has shown to be competitive when compared with a tailored method. Summary of Contribution: Column generation (CG) algorithms are among the most important and studied solution methods in operations research. CG algorithms are suitable to cope with large-scale problems arising from several real-life applications. The present paper proposes a generic stabilization framework to address two of the main issues found in a CG method: degeneracy in the master problem and massive instability of the dual variables. The newly devised method, called dynamic separation of aggregated rows (dyn-SAR), relies on an extended master problem that contains redundant constraints obtained by aggregating constraints from the original master problem formulation. This new formulation is solved in a column/row generation fashion. The efficacy of the proposed method is tested through an extensive experimental campaign, where we solve three different problems that differ considerably in terms of their constraints and objective function. Despite being a generic framework, dyn-SAR requires the embedded CG algorithm to be tailored to the application at hand.

Keywords: column generation; degeneracy; stabilization (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2021.1094 (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:orijoc:v:34:y:2022:i:2:p:1141-1156

Access Statistics for this article

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