Dual Inequalities for Stabilized Column Generation (StabCG)

稳定柱生成的对偶不等式 (StabCG)

• 批准号: 280866737
• 负责人: Professor Dr. Stefan Irnich
• 金额: --
• 依托单位: Lehrstuhl für BWL, insb. Logistikmanagement
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2017-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/280866737?language=en
• 关键词: Dual; Inequalities; Stabilized; Column; Generation

Many planning and optimization approaches are based on mixed-integer programming models and methods. Substantial progress has been made over the last 60 years, on the one hand driven by increased power of today's computers, on the other hand by various methodological achievements in mixed-integer programming. Column generation (CG) methods are among the most successful and important algorithms to deal with huge linear programs comprising many variables. Embedding CG in a branch-and-bound algorithm allows the solution of mixed-integer programs. Such methods are commonly referred to as a branch-and-price algorithms. Many successful branch-and-price algorithms can be found, for example, in the areas of vehicle routing, manpower planning, packing and cutting problems, sequencing and graph optimization. The main disadvantages of CG techniques can be attributed to instability of the values ¿¿of the dual variables. Previous techniques for mitigating the negative effects can be subsumed as "numerical methods of stabilization". Valério de Carvalho (2005: INFORMS Journal on Computing, 17 (2), 175-182) and Ben Amor et al. (2006: Operations Research, 54 (3), 454-463) have followed a different path for cutting stock and bin packing problems. They utilize properties of dual optimal solutions for stabilizing the CG process. Any dual optimal inequality (DOI) for the polyhedron of the optimal dual solutions can be added as an additional variable in the corresponding primal CG formulation. The dissertation (Gschwind 2014: Gutenberg School of Management and Economics, University of Mainz) developed a series of innovative concepts, which extend the existing literature on stabilized CG method using DOIs in several aspects.The overall objective of the research project is to improve exact methods for solving various problems. Compared to prior research, the project aims at solving larger and more difficult problem instances to proven optimality by developing new techniques for stabilizing CG method with DOIs. Previous findings from the literature and our own preliminary work supports the hypothesis that a successful stabilization can significantly improve CG methods in many applications.

许多规划和优化方法都基于混合整数规划模型和方法。过去 60 年取得了实质性进展，一方面是由于当今计算机能力的增强，另一方面是由于混合整数编程方面的各种方法论成就。列生成（CG）方法是处理包含许多变量的大型线性程序的最成功和最重要的算法之一。将 CG 嵌入分支定界算法中可以求解混合整数程序。此类方法通常称为分支价格算法。例如，在车辆路线、人力规划、包装和切割问题、排序和图形优化等领域可以找到许多成功的分支和价格算法。 CG 技术的主要缺点可归因于双变量值的不稳定。以前用于减轻负面影响的技术可以归为“稳定的数值方法”。 Valério de Carvalho (2005: INFORMS Journal onComputing, 17 (2), 175-182) 和 Ben Amor 等人。 (2006: Operations Research, 54 (3), 454-463) 采用了不同的方法来减少库存和装箱问题。他们利用双重最优解的特性来稳定 CG 过程。最优对偶解的多面体的任何对偶最优不等式 (DOI) 都可以作为附加变量添加到相应的原始 CG 公式中。该论文（Gschwind 2014：美因茨大学古腾堡管理与经济学院）提出了一系列创新概念，在多个方面扩展了使用 DOI 的稳定 CG 方法的现有文献。该研究项目的总体目标是改进解决各种问题的精确方法。与之前的研究相比，该项目旨在通过开发使用 DOI 稳定 CG 方法的新技术来解决更大、更困难的问题实例，以证明最优性。之前的文献研究结果和我们自己的初步工作支持了这样的假设：成功的稳定可以显着改善许多应用中的 CG 方法。