Dynamic Aggregation of Set-Partitioning Constraints in Column Generation

Issmail Elhallaoui (), Daniel Villeneuve (), François Soumis () and Guy Desaulniers ()
Additional contact information
Issmail Elhallaoui: Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Daniel Villeneuve: Kronos Inc., 3535 Queen Mary, Suite 650, Montréal, Québec, Canada H3V 1H8
François Soumis: Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Guy Desaulniers: Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7

Operations Research, 2005, vol. 53, issue 4, 632-645

Abstract: Column generation is often used to solve problems involving set-partitioning constraints, such as vehicle-routing and crew-scheduling problems. When these constraints are in large numbers and the columns have on average more than 8–12 nonzero elements, column generation often becomes inefficient because solving the master problem requires very long solution times at each iteration due to high degeneracy. To overcome this difficulty, we introduce a dynamic constraint aggregation method that reduces the number of set-partitioning constraints in the master problem by aggregating some of them according to an equivalence relation. To guarantee optimality, this equivalence relation is updated dynamically throughout the solution process. Tests on the linear relaxation of the simultaneous vehicle and crew-scheduling problem in urban mass transit show that this method significantly reduces the size of the master problem, degeneracy, and solution times, especially for larger problems. In fact, for an instance involving 1,600 set-partitioning constraints, the master problem solution time is reduced by a factor of 8.

Keywords: programming:linear; large-scale systems; column generation; degeneracy; dynamic constraint aggregation (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (22)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1050.0222 (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:53:y:2005:i:4:p:632-645

Access Statistics for this article

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