1

如何将线性规划 (LP) 问题的凸包表示为积分？是否有任何通用技术来执行此操作？

4

2 回答 2

3

在公式的意义上，线性程序产生一个具有（通常）分数极值点的多面体。如果你想完全解决这个问题，在多面体上没有什么可以改变/操作的。

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

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

这些算法用于计算整数点的凸包（或来自一般多面体），但它们并不简单且不“快速”。可以帮助您的软件可能是Porta或Polymake。

有一些属性描述了多面体/公式何时为整数。例如，其中之一被称为总（双）单模性。以这种方式制定您的问题或识别此属性并不容易，我不知道有任何结构性方法可以这样做。

我希望这有帮助 ：）

亲切的问候，

马丁

于 2014-02-26T10:14:27.970 回答
1

在上面的马丁回答中添加一点（我认为这对于评论来说太长了）：

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

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

当然，由于求解 LP 是多项式并且求解 ILP 是 NP 完全的，所以不能指望有一种通用的有效方法来完成您所期望的，因为这几乎会将 ILP 简化为 LP！

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

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

于 2014-02-27T08:26:39.650 回答