Gurobi produces different solutions for negligible constraint

Question

I am trying to allocate units of different products to different stores. For reasons that are not present in this toy example but are necessary in the full-scale implementation, I need a binary variable that indicates whether any units of a specific product are allocated to each particular store. Because this is a toy example, this variable is essentially "epiphenomenal" in its current implementation -- i.e. it is defined/constrained by the variable that informs my objective function, but it does not exert any influence on anything else. I assumed that because of this, gurobi would solve the exact same way no matter how I define this variable. However, that is not the case. Each time, the code runs and produces a solution within MIPs range. But the solution's objective value is numerically different. Moreover, the results look qualitatively different, with some solutions allocating high quantities of a product to a store and other solutions splitting product quantities heavily across all stores. Why is this so? How is gurobi implementing this so that I am encountering this problem? Is there a workaround?

I am using Python 3.5.5 64-bit and 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 ) ```

David Nehme · Accepted Answer · 2019-07-03T15:12:08.513

What you are describing is normal behavior of Gurobi and other MIP solvers. It looks for an optimal solution. We say "an optimal solution" not "the optimal solution" because in cases where there are multiple feasible solutions that have the same objective value (or even objective values within the optimality tolerance), there is no such thing as "the optimal solution". With some important exceptions, Gurobi is deterministic in that if you give it the same exact model run with the same library version on the same platform, it will give you the same result, but even changing the order of the constraints could change the result dramatically, as long as the solutions have similar objective function values. This is even before taking into account leaky abstractions that some MIPs are too difficult to solve in a reasonable amount of time.

The "work-around" in this case is to figure out which solutions you like better, quantify the why one solution is better than the other, then add that to the objective function.

Gurobi produces different solutions for negligible constraint

1 Answers1