线性规划凸壳的完整性

Question

如何将线性规划(LP)问题的凸壳表述为积分？有什么通用的技术来完成这个任务吗？

Answer 1

在上文对Martin的回答中再加一点(我认为这太长了，不能发表评论)：

1. 据我所知，有一个一般的过程叫做Chvátal过程，它允许通过添加Gomorry割集来最终描述凸包。这在理论上是非常有趣的；然而，有一个众所周知的例子，对于一个具有两个变量和两个约束的问题，这个过程采取n步骤(LP中的一个参数)，即增加的切数不能被问题的大小限制。
2. 完全单模矩阵在图论中的问题中是常见的，但它肯定不是一种“一般”方法:您可以通过定义TU矩阵中A矩阵的系数必须为0、1或-1来说服自己，当然，这在ILP中通常不是这样的。

当然，由于求解LP是多项式的，求解ILP是NP-完全的，所以不能期望有一种通用的有效方法来做您期望的事情，因为这几乎会将ILP减少到LP！

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

如果您有兴趣的话，我可以在周末提供进一步的参考资料。

Answer 2

在一个公式的意义上，一个线性规划产生一个多面体(一般)分数极值点。如果你想精确地解决这个问题，在多面体上没有什么可以改变的/manipulate。

如果您有一个(混合的)整数线性规划(MIP)，您可能对其整数点的凸包描述感兴趣。通常，这可以用于快速解决过程，因为您可以解决它的线性松弛，而不执行分支和定界过程之后。

这意味着，MIP的线性松弛给出了一个包含这个凸包的多面体，并且它本身不需要整数极值点。在许多情况下，您想要将这个公式收紧到整数点的凸包，这是由通常的求解者完成的(例如，通过添加不等式)。其目的始终是得到所述凸壳的公式。然而，找出这种配方通常是NP难的(因此没有已知的通用技术来容易获得它)。特别是这意味着，这种提法的规模(即不平等的数量)可以是指数的。

are算法用于计算整数点的凸壳(或从一般多面体)，但它们并不简单，也不是“快速”的。软件，可以帮助您，可能有波尔塔或多层制。

当多面体/公式是整数时，有一些性质描述。其中一个名字叫完全(对偶)单峰性。以这样的方式提出你的问题或识别这个属性并不容易，我也不知道有任何结构性的方法来这样做。

我希望这有帮助:)

致以亲切的问候，

马丁