Integral Column Generation for Set Partitioning Problems with Side Constraints

Adil Tahir (), Guy Desaulniers () and Issmail El Hallaoui ()
Additional contact information
Adil Tahir: Polytechnique Montréal and GERAD, Montréal, Quebec H3T 1J4 Canada; Mohammadia School of Engineers, Mohamed V University, Rabat 10090, Morocco
Guy Desaulniers: Polytechnique Montréal and GERAD, Montréal, Quebec H3T 1J4 Canada
Issmail El Hallaoui: Polytechnique Montréal and GERAD, Montréal, Quebec H3T 1J4 Canada

INFORMS Journal on Computing, 2022, vol. 34, issue 4, 2313-2331

Abstract: The integral column generation algorithm (ICG) was recently introduced to solve set partitioning problems involving a very large number of variables. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution. ICG combines the well-known column generation algorithm and a primal algorithm called the integral simplex using decomposition algorithm (ISUD). In this paper, we develop a generalized version of ICG, denoted I 2 CG, that can solve efficiently large-scale set partitioning problems with side constraints. This new algorithm can handle the side constraints in the reduced problem of ISUD, in its complementary problem, or in both components. Computational experiments on instances of the airline crew pairing problem (CPP) and the multidepot vehicle routing problem with time windows show that the latter strategy is the most efficient one and I 2 CG significantly outperforms basic variants of two popular column generation heuristics, namely, a restricted master heuristic and a diving heuristic. For the largest tested CPP instance with 1,761 constraints, I 2 CG can produce in less than one hour of computational time more than 500 integer solutions leading to an optimal or near-optimal solution. Summary of Contribution: In this paper, we develop a new integral column generation algorithm that can solve efficiently large-scale set partitioning problems with side constraints. The latter alter the quasi-integrality property needed for primal integral algorithms. The paper adds a methodological contribution remedying this issue. This remedy should, in our opinion, boost the use of primal exact methods, especially in the column generation context. The paper also has a computational contribution. Effectively, computational experiments on instances of the airline crew pairing problem and the multidepot vehicle routing problem with time windows are extensively discussed. We compare the proposed algorithm to basic variants of two popular column generation heuristics.

Keywords: discrete optimization; integral column generation; integral simplex using decomposition; aircrew pairing; vehicle routing with time windows (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1174 (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:4:p:2313-2331

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 ().