Gurobi производит различные решения для незначительного ограничения - PullRequest
Новая
       25

Gurobi производит различные решения для незначительного ограничения

1 голос
/ 19 июня 2019

Я пытаюсь распределить единицы разных товаров по разным магазинам.По причинам, которых нет в этом игрушечном примере, но которые необходимы в полномасштабной реализации, мне нужна двоичная переменная, которая указывает, выделены ли какие-либо единицы определенного продукта для каждого конкретного магазина.Поскольку это игрушечный пример, эта переменная по существу является "эпифеноменальной" в своей текущей реализации - то есть она определяется / ограничивается переменной, которая сообщает мою целевую функцию, но она не оказывает никакого влияния ни на что другое.Я предположил, что из-за этого gurobi будет решать точно так же, независимо от того, как я определяю эту переменную.Однако это не так.Каждый раз код запускается и создает решение в диапазоне MIP.Но объективное значение решения численно отличается.Кроме того, результаты выглядят качественно иными: некоторые решения распределяют большие количества товара по магазинам, а другие решения распределяют количество товара по всем магазинам.Почему это так?Как gurobi реализует это, чтобы я столкнулся с этой проблемой?Есть ли обходной путь?

Я использую Python 3.5.5 64-bit и gurobi 7.0.2 

# each entry is the number of units of that item in that store
x = [] 
for i in prod_range:
    x.append([])
    for j in loc_range:
        x[i].append( GRBmodel.addVar(vtype=GRB.INTEGER, obj=1, name='x_{}_{}'.format(i,j)) )
        var_name_list.append('x_{}_{}'.format(i,j))
    x[i].append( GRBmodel.addVar(vtype=GRB.INTEGER, obj=0, name='x_{}_{}'.format(i,j+1)) ) # the last loc is "unallocated" and incurs no revenue nor cost
    var_name_list.append('x_{}_{}'.format(i,j+1))
    GRBmodel.addConstr( x[i][j] >= 0, "constraint_0.{}_{}".format(i,j) )

# binary mask version of x
# should be 1 if there's any amount of that product in that store
y = []
for i in prod_range:
    y.append([])
    for j in loc_range:
        y[i].append( GRBmodel.addVar(vtype=GRB.BINARY, name='y_{}_{}'.format(i,j)) )
        var_name_list.append('y_{}_{}'.format(i,j))

GRBmodel.modelSense = GRB.MAXIMIZE

# all items assigned to some locations, including the "unallocated" loc
for i in prod_range: 
    GRBmodel.addConstr( sum(x[i][j] for j in loc_range) <= units_list[i], "constraint_1.1_{}".format(i) ) # notice in this "<=" way, x[i][unallocated] is free.

# not exceeding storage upper bounds or failing to meet lower bounds for each store
for j in loc_range:
    GRBmodel.addConstr( sum(x[i][j] for i in prod_range) <= max_units_relax * UB_units_list[j], "constraint_1.3_{}".format(j) ) # Update p9
    GRBmodel.addConstr( sum(x[i][j] for i in prod_range) >= LB_units_list[j], "constraint_1.4_{}".format(j) ) 

# test y. not sure why the answer is different when using 0.5 rather than 1
testInt = -10 # placeholder for break point
for i in prod_range:
    for j in loc_range:
        GRBmodel.addGenConstrIndicator( y[i][j], True, x[i][j], GRB.GREATER_EQUAL, 1 ) 
        GRBmodel.addGenConstrIndicator( y[i][j], False, x[i][j], GRB.LESS_EQUAL, 1 ) ```

1 Ответ

2 голосов
/ 22 июня 2019

То, что вы описываете, является нормальным поведением Gurobi и других решателей MIP. Он ищет оптимальное решение. Мы говорим « оптимальное решение», а не « оптимальное решение», потому что в тех случаях, когда существует несколько возможных решений, которые имеют одинаковое объективное значение (или даже объективные значения в пределах допуска оптимальности) нет такой вещи как " оптимальное решение". За некоторыми важными исключениями, Gurobi детерминирован в том, что если вы дадите ему ту же самую точную модель, запущенную с той же версией библиотеки на той же платформе, это даст вам тот же результат, но даже изменение порядка ограничений может значительно изменить результат До тех пор, пока решения имеют аналогичные значения целевой функции. Это даже до того, как принять во внимание неплотные абстракции , что некоторые MIP слишком сложны , чтобы решить их за разумное количество времени.

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

...