Multi-phase dynamic constraint aggregation for set partitioning type problems

• 成果类型: Article
• 署名作者: Elhallaoui, Issmail; Metrane, Abdelmoutalib; Soumis, Francois; Desaulniers, Guy
• 署名单位: Universite de Montreal; Polytechnique Montreal; Universite de Montreal
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-008-0254-5
• 发表日期: 2010
• 页码: 345-370
• 关键词: column generation approach; linear-programs; time windows; algorithm; optimization; degeneracy; vehicle

摘要

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.