Gurobi 为可忽略的约束产生不同的解决方案

Question

我正在尝试将不同产品的单位分配给不同的商店。出于这个玩具示例中不存在但在全面实施中必要的原因，我需要一个二进制变量来指示是否将特定产品的任何单位分配给每个特定商店。因为这是一个玩具示例，所以这个变量在其当前实现中本质上是 "epiphenomenal" —— 即通知我的 objective 函数的变量是 defined/constrained，但它不会施加任何影响在其他任何事情上。因此，我假设无论我如何定义这个变量，gurobi 都会以完全相同的方式求解。然而，事实并非如此。每次，代码都会运行并生成 MIP 范围内的解决方案。但是解决方案的 objective 值在数值上有所不同。此外，结果看起来在质量上有所不同，一些解决方案将大量产品分配给商店，而其他解决方案将产品数量大量分配给所有商店。为什么会这样？ gurobi 是如何实施的，以至于我遇到了这个问题？有解决方法吗？

我正在使用 Python 3.5.5 64 位和 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 ) ```

Answer 1

您所描述的是 Gurobi 和其他 MIP 求解器的正常行为。它会寻找最优解。我们说“一个最佳解决方案”而不是“最佳解决方案”，因为在存在多个具有相同[=24=的可行解决方案的情况下] 值（甚至 objective 值在最优容差范围内），不存在“ 最优解”这样的东西。除了一些重要的例外，Gurobi 是确定性的，因为如果你在同一平台上给它相同的模型运行和相同的库版本，它会给你相同的结果，但即使改变约束的顺序也可能只要解决方案具有相似的 objective 函数值，就会显着改变结果。这甚至在考虑 leaky abstractions that some MIPs are too difficult 在合理的时间内解决之前。

本例中的 "work-around" 是找出您更喜欢哪种解决方案，量化为什么一个解决方案比另一个更好，然后将其添加到 objective 函数中。

Gurobi 为可忽略的约束产生不同的解决方案

Gurobi produces different solutions for negligible constraint

python

linear-programming

gurobi