Gurobi missing optimal solutions?
AnsweredGreetings,
I am using Gurobi to attempt to map a set of N functions to a set of D devices. For starters, I'm mapping only 2 functions to 3 devices.
The problem was modeled by generating |N| batches of |D| binary decision variables:
# 5 -- Initiating variables
mappings = [i for i in range(len(costs))]
vars = []
# 6 -- Adding variables to the model
for i in range(len(nfs)):
batch = m.addVars(mappings, vtype=GRB.BINARY, name='map-func-'+str(i)+'-to-device-')
m.addConstr(sum(batch[v] for v in batch) == 1,
name='CONSTR-single-choice-'+str(i))
vars.append(batch)
# 7 -- Defining the objective function
for i in range(1, len(vars)):
for x in range(len(vars[i])):
for y in range(len(vars[i-1])):
objective += vars[i][x] * vars[i-1][y] * costs[x][y]
print(vars[i][x] * vars[i-1][y] * costs[x][y])
The objective function is to minimise the distance. To keep it simple, `costs` is a simple matrix with each hop costing 1. It is therefore expected that the optimal solutions are those in which both functions are mapped to the same device. Without any further constraints, Gurobi correctly returns those solutions:
Solution count 3: 0 0 0
No other solutions better than 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
[0.0, 0.0, 1.0, 0.0, 0.0, 1.0]
[1.0, 0.0, 0.0, 1.0, 0.0, 0.0]
[0.0, 1.0, 0.0, 0.0, 1.0, 0.0]
The trouble begins when when I add device capacity constraints. As I add them, I print them to the console. Gurobi misses one of the solutions:
# OBJECTIVE FUNCTION
0.0 + [ 0.0 map-func-1-to-device-[0] * map-func-0-to-device-[0] ]
0.0 + [ map-func-1-to-device-[0] * map-func-0-to-device-[1] ]
0.0 + [ 2.0 map-func-1-to-device-[0] * map-func-0-to-device-[2] ]
0.0 + [ map-func-1-to-device-[1] * map-func-0-to-device-[0] ]
0.0 + [ 0.0 map-func-1-to-device-[1] * map-func-0-to-device-[1] ]
0.0 + [ map-func-1-to-device-[1] * map-func-0-to-device-[2] ]
0.0 + [ 2.0 map-func-1-to-device-[2] * map-func-0-to-device-[0] ]
0.0 + [ map-func-1-to-device-[2] * map-func-0-to-device-[1] ]
0.0 + [ 0.0 map-func-1-to-device-[2] * map-func-0-to-device-[2] ]
# This is expected to be fulfilled.
# [1.0, 0.0, 0.0, 1.0, 0.0, 0.0] is a solution.
VARSET: [<gurobi.Var map-func-0-to-device-[0]>, <gurobi.Var map-func-1-to-device-[0]>]
<gurobi.TempConstr: 100.0 map-func-0-to-device-[0] + 500.0 map-func-1-to-device-[0] <= 60000>
<gurobi.TempConstr: 2.0 map-func-0-to-device-[0] + 50.0 map-func-1-to-device-[0] <= 4000>
<gurobi.TempConstr: 0.0 map-func-0-to-device-[0] + 50.0 map-func-1-to-device-[0] <= 1000>
<gurobi.TempConstr: 5.0 map-func-0-to-device-[0] + 300.0 map-func-1-to-device-[0] <= 2000>
<gurobi.TempConstr: map-func-0-to-device-[0] + 10.0 map-func-1-to-device-[0] <= 32>
<gurobi.TempConstr: 100.0 map-func-0-to-device-[0] + 25000.0 map-func-1-to-device-[0] <= 32000>
# Something amiss here. This solution is not included for some reason.
# Notice these constraints are almost a copy of the former.
# [0.0, 1.0, 0.0, 0.0, 1.0, 0.0] is a solution, but Gurobi does not include it.
VARSET: [<gurobi.Var map-func-0-to-device-[1]>, <gurobi.Var map-func-1-to-device-[1]>]
<gurobi.TempConstr: 100.0 map-func-0-to-device-[1] + 500.0 map-func-1-to-device-[1] <= 60000>
<gurobi.TempConstr: 2.0 map-func-0-to-device-[1] + 50.0 map-func-1-to-device-[1] <= 4000>
<gurobi.TempConstr: 0.0 map-func-0-to-device-[1] + 50.0 map-func-1-to-device-[1] <= 1000>
<gurobi.TempConstr: 5.0 map-func-0-to-device-[1] + 300.0 map-func-1-to-device-[1] <= 2000>
<gurobi.TempConstr: map-func-0-to-device-[1] + 10.0 map-func-1-to-device-[1] <= 32>
<gurobi.TempConstr: 100.0 map-func-0-to-device-[1] + 25000.0 map-func-1-to-device-[1] <= 32000>
# Two of the following constraints is violated.
# [0.0, 0.0, 1.0, 0.0, 0.0, 1.0] is correctly excluded.
VARSET: [<gurobi.Var map-func-0-to-device-[2]>, <gurobi.Var map-func-1-to-device-[2]>]
<gurobi.TempConstr: 50.0 map-func-0-to-device-[2] + 50.0 map-func-1-to-device-[2] <= 10000>
<gurobi.TempConstr: 2.0 map-func-0-to-device-[2] + 2500.0 map-func-1-to-device-[2] <= 1000>
<gurobi.TempConstr: 0.0 map-func-0-to-device-[2] + 0.0 map-func-1-to-device-[2] <= 0>
<gurobi.TempConstr: 0.0 map-func-0-to-device-[2] + 0.0 map-func-1-to-device-[2] <= 0>
<gurobi.TempConstr: map-func-0-to-device-[2] + 24.0 map-func-1-to-device-[2] <= 24>
<gurobi.TempConstr: 5.0 map-func-0-to-device-[2] + 5.0 map-func-1-to-device-[2] <= 0>
Set parameter PoolSearchMode to value 2
Set parameter PoolGap to value 1
Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (linux64 - "Ubuntu 20.04.6 LTS")
CPU model: AMD Ryzen 5 5500U with Radeon Graphics, instruction set [SSE2|AVX|AVX2]
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 20 rows, 6 columns and 36 nonzeros
Model fingerprint: 0xc6fc2e2d
Model has 6 quadratic objective terms
Variable types: 0 continuous, 6 integer (6 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+04]
Objective range [0e+00, 0e+00]
QObjective range [2e+00, 4e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 6e+04]
Presolve removed 20 rows and 4 columns
Presolve time: 0.00s
Presolved: 0 rows, 2 columns, 0 nonzeros
Variable types: 0 continuous, 2 integer (2 binary)
Found heuristic solution: objective 0.0000000
Root relaxation: objective 0.000000e+00, 0 iterations, 0.00 seconds (0.00 work units)
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - 0 0.00000 0.00000 0.00% - 0s
Optimal solution found at node 0 - now completing solution pool...
Nodes | Current Node | Pool Obj. Bounds | Work
| | Worst |
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 - 0 - 0.00000 - - 0s
0 0 - 0 - 0.00000 - - 0s
0 0 cutoff 0 - 0.00000 - - 0s
Explored 1 nodes (0 simplex iterations) in 0.02 seconds (0.00 work units)
Thread count was 12 (of 12 available processors)
Solution count 1: 0
No other solutions better than 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
[1.0, -0.0, 0.0, 1.0, 0.0, 0.0]
Is there any way I can debug Gurobi's process in finding these solutions? I've been searching for ways to investigate which constraints are valid, but apparently I can only do that when the model is infeasible.
-
Hi Rui,
Just to be sure - Unless you're using the solution pool functionality, Gurobi does not necessarily return all optimal solutions.
In general, if you feel a solution should be returned (and considered feasible) while Gurobi does not generate it, what you should do is fix the variables to exactly that solution. So for each variable, set its LB and UB attributes to the value you have in mind. Then ask Gurobi to solve the model. You should now see one of these cases:
- Gurobi returns your solution; you should inspect the objective function value. Perhaps it's worse than the solution Gurobi previously found, which could indicate an issue with data or model. Or, it has the same objective function value but Gurobi just ended up returning another, equally optimal solution.
- Gurobi says the model is infeasible. In this case, you can use functionality like computeIIS and feasRelax to understand why the solution is considered infeasible.
Kind regards,
Ronald0 -
A related article in the Knowledge Base is Why does Gurobi report my model is infeasible when it has a feasible solution?
0 -
Hi! Many thanks for the prompt responses.
- I am indeed using SolutionPools.
# Parameters
m.Params.PoolSearchMode = 2 # Value of 2 means find the n best solutions
m.Params.PoolSolutions = 10 # Number n of solutions to find
m.Params.PoolGap = 0.0 # Tolerance gap for optimal value - I tried fixing the lower and upper bounds of the variables leading to the other feasible solution. That solution is indeed returned, and the objective function value is the same. The former solution, [1.0, 0.0, 0.0, 1.0, 0.0, 0.0], is no longer returned in this case.
Solution count 1: 0
No other solutions better than 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
[0.0, 1.0, 0.0, 0.0, 1.0, 0.0] - I've also tried setting other parameters that have to do with numerical issues (and even tried combinations of each), but to no avail:
m.Params.IntFeasTol = 1e-1 # Also tried 1e-9
m.Params.IntegralityFocus = 1
m.Params.Heuristics = 0 - If my interpretation of the article is correct, the printed statistics and quality do not seem to hint at any numerical issues:
Statistics for model mip:
Linear constraint matrix : 20 Constrs, 6 Vars, 36 NZs
Variable types : 0 Continuous,
6 Integer (6 Binary)
Matrix coefficient range : [ 1, 25000 ]
Objective coefficient range : [ 0, 0 ]
Variable bound range : [ 1, 1 ]
RHS coefficient range : [ 1, 60000 ]
Solution quality statistics for model mip :
Maximum violation:
Bound : 0.00000000e+00
Constraint : 0.00000000e+00
Integrality : 0.00000000e+00
0 - I am indeed using SolutionPools.
-
Hello again!
I found a parameter that worked! m.Params.Presolve = 0 fixed it. Both solutions are now correctly printed:
Solution count 2: 0 0
No other solutions better than 0
Optimal solution found (tolerance 1.00e-04)
Best objective 0.000000000000e+00, best bound 0.000000000000e+00, gap 0.0000%
[0.0, 1.0, 0.0, 0.0, 1.0, 0.0]
[1.0, 0.0, 0.0, 1.0, 0.0, 0.0]Also tried toying with m.Params.Aggregate = 0 and m.Params.NumericFocus = 3, but these did not change the result.
0 -
Does the latest version of Gurobi (12.0.0) also fail to find one of the optimal solutions when setting PoolSearchMode to 2? If so, can you please write out an MPS model file and post the file contents here?
m.write("model.mps")
0 -
@Eli, here is a MRE on a smaller (but similar) model for v12
m = gp.Model()
x = m.addVars(2, vtype="B", name="x")
y = m.addVars(2, vtype="B", name="y")
m.setObjective(y[0]*x[1] + y[1]*x[0])
m.addConstr(x.sum() == 1)
m.addConstr(y.sum() == 1)
m.params.PoolSearchMode=2
m.params.PoolGap=0
#m.params.Symmetry=0 # uncomment to get both valid solutions
m.optimize()Symmetry seems to be at play. Adding a continuous variable to the model is also enough to avoid the buggy behavior.
0 -
Hi Rui,
I'll open a support request in our Gurobi Help Center to continue the discussion on this issue. You will receive an email shortly.
- Riley
0 -
Greetings once more,
Thank you for the responses, for setting up the support thread, and for providing the workarounds!
I deduce it is no longer necessary to test in Gurobi v12.0.0? It doesn't seem to be available for me to install using pip. Is it possible my system is not compatible with the latest version? I'm on Ubuntu 20.04.
rui@rui-Lenovo-V15-G2-ALC:~$ python3 -m pip install gurobipy --upgrade
Requirement already up-to-date: gurobipy in ./.local/lib/python3.8/site-packages (11.0.3)
rui@rui-Lenovo-V15-G2-ALC:~$ python3 -m pip install gurobipy==12.0.0
ERROR: Could not find a version that satisfies the requirement gurobipy==12.0.0 (from versions: 9.1.0, 9.1.1, 9.1.2, 9.5.0, 9.5.1, 9.5.2b0, 9.5.2, 10.0.0b1, 10.0.0, 10.0.1, 10.0.2, 10.0.3, 11.0.0b1, 11.0.0, 11.0.1, 11.0.2, 11.0.3)
ERROR: No matching distribution found for gurobipy==12.0.00 -
Hi Rui,
No need to test V12, we have done this already, thanks.
You'll need a more recent version of Python to use Gurobi V12.
See the following article for details
https://support.gurobi.com/hc/en-us/articles/360013195212-Which-Python-versions-are-supported-by-Gurobi- Riley
0
Please sign in to leave a comment.
Comments
9 comments