Перечислите решения в Gurobi - PullRequest
Новая
       71

Перечислите решения в Gurobi

0 голосов
/ 20 сентября 2019

У меня проблема ЛП без какой-либо цели, т.е. она выглядит как Ax <= B. Теперь допустимое множество содержит потенциально бесконечное множество решений.Есть ли способ перечислить разные решения, которые разумно отличаются друг от друга? </p>

Пока я использую этот код, который выбирает функцию случайной оптимизации, надеясь, что это приведет к различным решениям. 

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?

1 Ответ

0 голосов
/ 20 сентября 2019

Ваш подход, конечно, является совершенно правильным методом для отбора различных решений.Еще один возможный способ - перечислить все основные возможные решения (угловые точки).Однако не все так просто.Для этого есть интересный трюк: используйте двоичные переменные для кодирования базиса (0 = неосновная, 1 = базовая), а затем используйте пул решений Gurobi для перечисления всех возможных целочисленных решений.Это даст вам все основные возможные решения.Подробнее см. ссылка .

...