期刊
MATHEMATICAL PROGRAMMING
卷 152, 期 1-2, 页码 113-146出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-014-0779-8
关键词
Interior point methods; Warmstarting; Column generation; Linear programming; Cutting stock problem; Vehicle routing problem with time windows
类别
资金
- Facultad de Ingenieria, Universidad del Desarrollo
- Beca Presidente de la Republica (CONICYT) from Chile
- UK Engineering and Physical Sciences Research Council (EPSRC) [EP/G060169/1]
- EPSRC [EP/G060169/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/G060169/1] Funding Source: researchfish
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据