Multi-phase dynamic constraint aggregation for set partitioning type problems |
| |
Authors: | Issmail Elhallaoui Abdelmoutalib Metrane François Soumis Guy Desaulniers |
| |
Institution: | 1. Département de Mathématiques et de Génie Industriel, école Polytechnique and GERAD, C.P. 6079, Succ. Centre-Ville, Montreal, QC, H3C 3A7, Canada
|
| |
Abstract: | Dynamic constraint aggregation is an iterative method that was recently introduced to speed up the linear relaxation solution
process of set partitioning type problems. This speed up is mostly due to the use, at each iteration, of an aggregated problem
defined by aggregating disjoint subsets of constraints from the set partitioning model. This aggregation is updated when needed
to ensure the exactness of the overall approach. In this paper, we propose a new version of this method, called the multi-phase
dynamic constraint aggregation method, which essentially adds to the original method a partial pricing strategy that involves
multiple phases. This strategy helps keeping the size of the aggregated problem as small as possible, yielding a faster average
computation time per iteration and fewer iterations. We also establish theoretical results that provide some insights explaining
the success of the proposed method. Tests on the linear relaxation of simultaneous bus and driver scheduling problems involving
up to 2,000 set partitioning constraints show that the partial pricing strategy speeds up the original method by an average
factor of 4.5. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|