Operations Research
HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
QUICK SEARCH:   [advanced]


     

OPERATIONS RESEARCH
Vol. 53, No. 4, July-August 2005, pp. 632-645
DOI: 10.1287/opre.1050.0222
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Citing Articles
Right arrow Citing Articles via HighWire
Right arrow Citing Articles via Google Scholar
Google Scholar
Right arrow Articles by Elhallaoui, I.
Right arrow Articles by Desaulniers, G.
Right arrow Search for Related Content

Dynamic Aggregation of Set-Partitioning Constraints in Column Generation

Issmail Elhallaoui, Daniel Villeneuve, François Soumis, Guy Desaulniers

Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Kronos Inc., 3535 Queen Mary, Suite 650, Montréal, Québec, Canada H3V 1H8
Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
Mathematics and Industrial Engineering Department, École Polytechnique de Montréal and GERAD, Montréal, Québec, Canada H3C 3A7
issmail.elhallaoui{at}gerad.ca
dvilleneuve{at}kronos.com
francois.soumis{at}gerad.ca
guy.desaulniers{at}gerad.ca

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.

Subject classifications: programming:linear; large-scale systems; column generation; degeneracy; dynamic constraint aggregation.
History: Received July 2003; revision received January 2004; revision received April 2004; accepted June 2004.




This article has been cited by other articles:


Home page
 INFORMS Journal on ComputingHome page
S. Subramanian and H. D. Sherali
An Effective Deflected Subgradient Optimization Scheme for Implementing Column Generation for Large-Scale Airline Crew Scheduling Problems
INFORMS Journal on Computing, September 1, 2008; 20(4): 565 - 578.
[Abstract] [PDF]

Home page
 Operations ResearchHome page
M. E. Lubbecke and J. Desrosiers
Selected Topics in Column Generation
Operations Research, November 1, 2005; 53(6): 1007 - 1023.
[Abstract] [PDF]


HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
Copyright © 2005 by INFORMS.