线性规划凸包中的集成性

Question

怎样才能将线性规划（LP）问题的凸包形式化为积分？是否有任何通用技术来执行此操作？

Answer 1

增添几分马丁回答上面的（我认为这是太长了评论）：

1. 有一个我知道的通用程序，称为Chvátal-Gomorry程序，它允许通过添加Gomorry切割来最终描述凸包。理论上这非常有趣;然而，有一个众所周知的例子，其中该程序采用n步骤（LP中的参数）解决具有两个变量和两个约束的问题，即，所添加的切口数目不能受问题的大小限制。

2. 完全单模矩阵在图论中出现的问题很常见，但它肯定不是一个“通用”方法：你可以通过定义说服你自己，即矩阵的系数必须是0,1或 - 1在TU矩阵中，当然这在ILP中通常不是这种情况。

当然，因为解决一个LP是多项式和解决的ILP是NP完全，一个不能指望有做你所期望的一个普遍有效的方法，因为这将几乎减少ILP向LP！

但是，如果你正在研究一个特别的问题，特别是如果它有一个简单的结构，它可能是上述两种方法之一有效的“特殊情况”之一。

如果您有兴趣，我可以在本周末提供更多参考。

Answer 2

从一个公式的意义上说，一个线性程序产生一个多边形（一般来说）分数极值点。如果你想解决这个问题，在多面体上没有任何改变/操作。

如果您有一个（混合）整数线性程序（MIP），您可能会对其整数点的凸包的描述感兴趣。一般来说，这可以用于快速解决方案过程，因为您可以解决其线性松弛问题，而无需事后执行分支和绑定过程。

这意味着，MIP的线性松弛给出了一个包含这个凸包的多面体 - 它本身不需要有整数的极值点。在许多情况下，您希望通过常规求解器（例如，通过添加不等式）将此公式收紧至整数点的凸包。 目标总是获得所述凸包的配方。然而，找到这个公式通常是NP-hard（所以没有已知的通用技术可以很容易地获得）。尤其是，这意味着这种公式的大小（即不等式的数量）可以是指数的。

算法是计算整数点（或从一般多面体）的凸包，但它们并不简单，也不“快”。软件，它可以帮助你可能是Porta或Polymake。

有多个属性描述多面体/配方是整数。例如。其中一个名称为total (dual) unimodularity。以这种方式制定您的问题或识别此属性并不容易，我也不知道有任何结构性方法可以做到这一点。

我希望这有助于:)

亲切的问候，

马丁