The Group-Theoretic Approach in Mixed Integer Programming
The Group-Theoretic Approach in Mixed Integer Programming
复制标题
混合整数规划中的群论方法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Santanu S. Dey
中科院分区：
文献类型：
--
作者：
Jean;Santanu S. Dey
在本章中，我们概述了混合整数规划中群论方法的数学基础和最新的理论和计算进展。我们从几何上激发了群松弛的定义，并给出了在这个集合上优化线性函数的方法。然后讨论了群弛豫结构的基本结果。我们描述了各种最近的方法来推导主群松弛的有效不等式，并回顾了一般的证明技术来证明这些集合的候选不等式是强的（极端的）。最后，我们讨论了从计算研究中获得的见解，这些研究旨在测量混合整数规划的群论松弛和切割平面的强度。
In this chapter, we provide an overview of the mathematical foundations and recent theoretical and computational advances in the study of the grouptheoretic approach in mixed integer programming. We motivate the definition of group relaxation geometrically and present methods to optimize linear functions over this set. We then discuss fundamental results about the structure of group relaxations. We describe a variety of recent methods to derive valid inequalities for master group relaxations and review general proof techniques to show that candidate inequalities are strong (extreme) for these sets. We conclude by discussing the insights gained from computational studies aimed at gauging the strength of grouptheoretic relaxations and cutting planes for mixed integer programs.