我有一个线性问题，即找到满足所有约束的所有解决方案。例如，我的变量是 = [0.323, 0.123, 1.32, 6.3...] 是否可以获得例如按适应度（最大化/最小化）函数排序的前 100 个解决方案？
问问题
1496 次
2 回答
2
在连续 LP 中枚举不同的解决方案是一个困难的概念。例如考虑max x, s.t. x <= 1。显然x=1，x=0.99999是解决方案，因此之间的无限数量的解决方案。我们可以列举“角落解决方案”（或基本解决方案）。有关示例，请参见此处。这种方案可以适应于找到按目标排序的前 100 个不同的角点。对于具有离散变量的模型，许多约束规划求解器将使您有可能找到许多解决方案。
于 2016-06-07T20:22:32.857 回答
0
如果您可以按照建议定义适应度函数，那么您可能首先要求解最大化该函数的 LP。之后，您可以包含一个客观截止值，迫使您的第二个解决方案比第一个解决方案稍差。您可以通过在 的右侧引入一个作为目标函数的切割来实现这一点optimal value - epsilon。
当然，这不会为您提供所有（基本）解决方案，但您可能会发现哪些变量始终具有相同的值，或者不同解决方案之间存在多少差异。
于 2016-06-08T08:22:37.083 回答