A new warmstarting strategy for the primal-dual column generation method

• 成果类型: Article
• 署名作者: Gondzio, Jacek; Gonzalez-Brevis, Pablo
• 署名单位: University of Edinburgh; Heriot Watt University; Universidad del Desarrollo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0779-8
• 发表日期: 2015
• 页码: 113-146
• 关键词: interior-point methods; warm-start strategies; shortest-path problem; cutting plane method; Combinatorial Optimization; linear program; algorithm; DECOMPOSITION; constraints

摘要

This paper presents a new warmstarting technique in the context of a primal-dual column generation method applied to solve a particular class of combinatorial optimization problems. The technique relies on calculating an initial point and on solving auxiliary linear optimization problems to determine the step direction needed to fully restore primal and dual feasibilities after new columns arrive. Conditions on the maximum size of the cuts and on a suitable initial point are discussed. Additionally, the strategy ensures that the duality gap of the warmstart is bounded by the old duality gap multiplied with a (small) constant, which depends on the relation between the old and modified problems. Computational experiments demonstrate the gains achieved when compared to a coldstart approach.