在 Gurobi 中枚举解决方案

Question

我有一个没有任何目标的 LP 问题，即它看起来像 Ax <= B. Now the feasible set contains potentially infinitely many solutions. Is there any way to enumerate different solutions, which are reasonably different among each other?

现在，我正在使用这段选择随机优化函数的代码，希望能产生不同的解决方案。

import gurobipy as gp
import numpy as np


def solve(A, B):
    model = gp.Model()
    model.Params.OutputFlag = False
    x = model.addVars(A.shape[1]).values()
    for a, b in zip(A, B):
        expr = gp.LinExpr(b)
        expr.addTerms(a, x)
        model.addConstr(expr <= 0)

    expr = gp.LinExpr()
    for x_ in x:
        if np.random.random() < 0.5:
            expr.add(x_)
        else:
            expr.add(-x_)

    model.setObjective(expr, gp.GRB.MAXIMIZE)

    model.optimize()

    return np.array([x_.x for x_ in x])


n_constr = 6
n_var = 5

A = np.random.random((n_constr, n_var)) * 2 - 1
B = np.random.random((n_constr,)) * 2 - 1

for i in range(3):
    print(solve(A, B))

一个样本输出

[ 1.59465412  0.          0.         -0.77579453  0.        ]
[-1.42381457  0.          0.         -7.70035252 -8.55823707]
[1.8797086  0.         0.         7.24494007 4.43847791]

有什么优雅的Gurobi具体解决方案吗？

Answer 1

您的方法当然是对不同解决方案进行采样的完全有效的方法。另一种可能的方法是枚举所有基本可行的解决方案（角点）。然而并不那么容易。对此有一个有趣的技巧：使用二进制变量对基础进行编码（0=非基础，1=基础），然后使用 Gurobi 解决方案池枚举所有可行的整数解决方案。这将为您提供所有基本可行的解决方案。有关详细信息，请参阅链接。

Answer 2

我认为这取决于你所说的合理不同的意思。如果您想要间隙为 1 的解决方案，Erwin 建议的方法很有效。如果您想要间隙为 0.5 的解决方案，请定义一个虚拟变量

Z = 2X

并将 Z 设置为整数，将 X 设置为连续。然后，您可以使用 Gurobi 中的解决方案池来枚举任意数量的解决方案（使用

PoolSolutions

参数 Link 指定。类似地，您可以改变

Z = k X

中的因子 k 以在某个间隙获得解决方案。您不一定使用解决方案池时必须设置任何目标。在这种情况下，不要定义

PoolGap

参数。