时间戳

首页 > 解决方案 > 在 Gurobi 中枚举解决方案

python - 在 Gurobi 中枚举解决方案

问题描述

我有一个没有任何目标的 LP 问题，即它看起来像 Ax <= B。现在可行集可能包含无限多的解决方案。有没有办法枚举不同的解决方案，这些解决方案彼此之间存在合理的差异？

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

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 特定解决方案？

标签： pythonlinear-programminggurobi

解决方案

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

推荐阅读