在python中获取GLPK solver为LP计算的前10个次优解

Question

我正在尝试使用GLPK解决LP问题。我的问题是计算机网络中的路由问题。给定网络拓扑和每个链路容量以及网络中每个源-目的地对的流量需求矩阵，我希望最小化网络中的最大链路利用率。这是一个LP问题，我知道如何使用GLPK获得最佳解决方案

我的问题是我也想得到次优解。有什么方法可以让我得到GLPK的前10个次优解决方案吗

最好的

Answer 1

对于纯LP（只有连续变量），找到“次优”解的概念非常困难（只需移开一个ε，就有了另一个解）。我们可以用不同的定义：找到“下一个最佳”的角点（也称为基准）。这并不是那么容易做到的，但是使用二进制变量（link）对基进行编码有一种比较复杂的方法

如果问题实际上是一个MIP（带有二进制变量），则更容易找到“次优”解决方案。一些高级解算器为此内置了工具（称为：解决方案池）。注意：glpk没有此选项。或者，我们也可以通过添加一个禁止最佳解决方案的切割来实现这一点，然后解析（link）。在本例中，我们利用了一些结构。从here导出了0-1变量的一般割集。对于一般的整数变量也可以这样做，但是事情会变得有点混乱