Dynamic aggregation of set-partitioning constraints in column generation
成果类型：
Article
署名作者：
Elhallaoui, I; Villeneuve, D
署名单位：
Universite de Montreal; Polytechnique Montreal; Universite de Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1050.0222
发表日期：
2005
页码：
632-645
关键词：
摘要：
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.