線性規劃凸包中的集成性

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。以這種方式制定您的問題或識別此屬性並不容易，我也不知道有任何結構性方法可以做到這一點。

我希望這有助於:)

親切的問候，

馬丁