Dual Inequalities for Stabilized Column Generation (StabCG)

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

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.