混合整數編程可以解決多少個決策變量？

我有一個混合整數編程問題（二進制整數變量），我可以解決多少個變量，即上限和將花費的時間？混合整數編程可以解決多少個決策變量？

該問題會有最大的約束和最小化成本函數，但變量是m * n矩陣的形式。所以，問題是可能是m和n的最大值，也是完成計算所需的時間？

使用COIN CBC，GLPK，CPLEX，GUROBI等標準軟件/庫。

來源

2016-03-16 Yashwanth Remidi

如果您有最多5個約束，那麼'm'和'n'是什麼？ – vcp

m * n是決策變量矩陣，而不是約束，我定義了約束條件，求解器用m * n個變量解決問題，並給出了最佳變量作爲解決方案。市場上解算器可以解決的m * n的最大尺寸是多少？ –

真的可以使用市場上可用的開源/商業解決方案來解決它嗎？

簡答：是的，它可以解決數以百萬計的決策變量MIP。

理論

一般而言MIP是NP-hard problem，並且不能在多項式時間爲O（n^k）的來解決。也是不直接來確定什麼是MIP輸入「n」的問題。不是。行，列或其產品，矩陣性質A，決策變量的性質，MIP和寬鬆LP之間的差距？

如果IP製劑（組Ax = b）中，矩陣A是totally unimodular，和所有係數是整數，則LP鬆弛的溶液也是IP的溶液中，並因此引起問題的複雜性是多項式 。

如果不是，那麼在一般情況下，您應該預期該問題是NP-hard。作爲一個拇指規則，變量越多，約束越多，問題越難。

實踐

MIP/LP求解器可以使用各種技術/算法來解決在合理的時間有任何問題（以小時計），特別是如果你是不是在找「」最佳整數解，並願意接受解決方案關閉最優。

沒有固定的尺寸限制 - 即使在標準筆記本電腦和臺式計算機上，Gurobi Optimizer也能定期解決具有數百萬變量和約束條件的模型。更重要的是，您可以在Gurobi的表現中看到結果，尤其是在更大，更難的模型上。事實上，Gurobi最近解決了MIPLIB2010庫中的11個模型，這些模型以前沒有被其他解算器解決過。

來源：http://www.gurobi.com/products/gurobi-optimizer

特殊MIP問題

特殊的技術可用來解決MIP的特殊情況。

Cutting stock problem
bin packing problem：將料問題的特殊情況。

我寫了簡單的列生成算法來解決切割庫存問題。請參閱https://github.com/vcphub/cspsol

來源

2016-03-16 05:42:21 vcp

是的，正是我想問的是，我有一個MIP問題，我嘗試使用Excel解決，它在200個變量（〜50分鐘）之後超出了最大值，但是我想要將它擴展到1M +決策變量2-3小時）。真的有可能使用市場上可用的開源/商業解決方案來解決它嗎？ –

是的，這是可能的。試試免費軟件GLPK。 – vcp

是的，它*可能*是可能的。但是，如果您使用的是免費/開源解決方案，那麼您必須很幸運才能解決它「開箱即用」的問題。如果您的問題具有良好的結構和良好的數字特徵，那麼可能是好的。但它可能不會 - 目前我的問題只有大約27k個整數變量，並且對於某些實例，合理服務器上的CPLEX無法在8小時內找到整數解決方案。如果您可以通過求解器（如列生成，Benders或VLNS）實現一些聰明的技巧，您可能會獲得更好的性能並解決更大的問題。順便說一句：Excel解算器非常薄弱。 – TimChippingtonDerrick

混合整數編程可以解決多少個決策變量？

回答

相關問題