Integral column generation for the set partitioning problem

Adil Tahir (), Guy Desaulniers () and Issmail El Hallaoui ()
Additional contact information
Adil Tahir: GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal
Guy Desaulniers: GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal
Issmail El Hallaoui: GERAD and Department of Mathematics and Industrial Engineering, Polytechnique Montréal

EURO Journal on Transportation and Logistics, 2019, vol. 8, issue 5, No 10, 713-744

Abstract: Abstract The integral simplex using decomposition (ISUD) algorithm was recently developed to solve efficiently set partitioning problems containing a number of variables that can all be enumerated a priori. This primal algorithm generates a sequence of integer solutions with decreasing costs, leading to an optimal or near-optimal solution depending on the stopping criterion used. In this paper, we develop an integral column generation (ICG) heuristic that combines ISUD and column generation to solve set partitioning problems with a very large number of variables. Computational experiments on instances of the public transit vehicle and crew scheduling problem and of the airline crew pairing problem involving up to 2000 constraints show that ICG clearly outperforms two popular column generation heuristics (the restricted master heuristic and the diving heuristic). ICG can yield optimal or near-optimal solutions in less than 1 hour of computational time, generating up to 300 integer solutions during the solution process.

Keywords: Discrete optimization; Column generation; Integral simplex using decomposition; Crew scheduling (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s13676-019-00145-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:eurjtl:v:8:y:2019:i:5:d:10.1007_s13676-019-00145-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13676

DOI: 10.1007/s13676-019-00145-6

Access Statistics for this article

EURO Journal on Transportation and Logistics is currently edited by Michel Bierlaire

More articles in EURO Journal on Transportation and Logistics from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().