在Google或工具中獲取所有解決方案

Question

我有一個線性問題，即找到滿足所有約束條件的所有解決方案。 例如，我的變量是= [0.323,0.123,1.32,6.3 ...] 是否有可能得到例如按健身（最大化/最小化）函數排序的前100個解決方案？

Answer 1

在連續的LP列舉不同的解決方案是一個困難的概念。例如。考慮max x, s.t. x <= 1。很明顯，x=1,x=0.99999是解決方案，它們之間也有無數的解決方案。我們可以列舉「角落解決方案」（或基本解決方案）。一個例子見here。可以調整這種方案以找到按目標排序的前100個不同角點。對於具有離散變量的模型，許多約束規劃解算器將爲您提供找到許多解決方案的可能性。

Answer 2

如果您可以按照您的建議定義適應度函數，那麼您可能首先需要解決使該函數最大化的LP。之後，你可以包含一個客觀的截止點，強制你的第二個解決方案比第一個解決方案稍差。您可以通過在optimal value - epsilon的右側引入一個作爲目標函數的剪輯來實現此目的。

當然，這將而不是給你所有（基本）的解決方案，但你可能會發現哪些變量總是在相同的價值或不同的解決方案之間有多少差異。