Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems
Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems
复制标题
二进制混合整数规划问题的 Dantzig-Wolfe 重构分类
DOI：
10.1016/j.ejor.2009.11.014
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
R. Jans
中科院分区：
文献类型：
--
作者：
R. Jans
在这篇文章中，我们提供了一个分类的Dantzig-Wolfe重新制定的二元混合可编程问题。我们特别专注于在Dantzig-Wolfe分解的凸化方法中对二元条件进行建模。对于一般的二元混合规划问题，总问题的极值点不一定对应于子问题的极值点。因此，二进制条件一般不能施加在新的主问题变量上，但必须施加在原始的二进制变量上。然而，在某些情况下，可以直接对新的主问题变量施加二进制限制。在文献中，对于MIP问题，对原始变量与主问题变量施加二元条件的问题还没有系统地讨论过，大多数研究都集中在纯二元情况下。该分类指出了在哪些情况下您可以和不可以对新的主问题变量施加二元条件。
In this note, we provide a classification of Dantzig–Wolfe reformulations for Binary Mixed Integer Programming Problems. We specifically focus on modeling the binary conditions in the convexification approach to the Dantzig–Wolfe decomposition. For a general Binary Mixed Integer Programming problem, an extreme point of the overall problem does not necessarily correspond to an extreme point of the subproblem. Therefore, the binary conditions cannot in general be imposed on the new master problem variables but must be imposed on the original binary variables. In some cases, however, it is possible to impose the binary restrictions directly on the new master problem variables. The issue of imposing binary conditions on the original variables versus the master problem variables has not been discussed systematically for MIP problems in general in the literature and most of the research has been focused on the pure binary case. The classification indicates in which cases you can, and cannot, impose binary conditions on the new master problem variables.