Column generation for extended formulations
Column generation for extended formulations
复制标题
用于扩展配方的色谱柱生成
DOI：
--
复制
发表时间：
2011
影响因子：
2.4
通讯作者：
François Vanderbeck
中科院分区：
文献类型：
--
作者：
R. Sadykov;François Vanderbeck
在扩展的变量空间中工作，可以为混合整数规划开发更紧密的重构。然而，扩展公式的大小快速增长太大，无法通过MIP求解器进行直接处理。然后，可以使用通过动态生成变量和约束来定义和改进的内部近似。当扩展公式源于子问题的重新公式化时，可以使用Dantzig-Wolfe分解范式实现扩展公式的列生成。定价子问题的解决方案表示在变量的扩展配方和添加到当前的限制版本的扩展配方沿着的子问题的约束，是积极的子问题的解决方案。这个所谓的“列和行生成”的过程是在这里重新统一介绍，概括列生成算法，并扩展到与近似扩展配方的情况下工作。机器调度，装箱，广义分配，和多级批量问题的数值方法的兴趣进行评估。我们比较直接处理的扩展配方，一个标准的列生成方法，和“列和行生成”的程序，突出后者的一个关键好处：提升定价问题的解决方案在空间的扩展配方允许他们重组成新的子问题的解决方案，并导致更快的收敛。
Working in an extended variable space allows one to develop tighter reformulations for mixed integer programs. However, the size of the extended formulation grows rapidly too large for a direct treatment by a MIP-solver. Then, one can work with inner approximations defined and improved by generating dynamically variables and constraints. When the extended formulation stems from subproblems’ reformulations, one can implement column generation for the extended formulation using a Dantzig–Wolfe decomposition paradigm. Pricing subproblem solutions are expressed in the variables of the extended formulation and added to the current restricted version of the extended formulation along with the subproblem constraints that are active for the subproblem solutions. This so-called “column-and-row generation” procedure is revisited here in a unifying presentation that generalizes the column generation algorithm and extends to the case of working with an approximate extended formulation. The interest of the approach is evaluated numerically on machine scheduling, bin packing, generalized assignment, and multi-echelon lot-sizing problems. We compare a direct handling of the extended formulation, a standard column generation approach, and the “column-and-row generation” procedure, highlighting a key benefit of the latter: lifting pricing problem solutions in the space of the extended formulation permits their recombination into new subproblem solutions and results in faster convergence.