Check heuristics for each solution
Ongoing
Good morning,
I have modelled a problem and it works perfectly. I don't have an objective function. I get 100 solutions with this configuration:
m.setParam('PoolSearchMode',1)
m.setParam('PoolSolutions',100)
Then, I save all solutions and I apply (in another source code) an heuristic to all of them to check temporal constraints (that are not implemented in Gurobi) and calculate a function and I select the solution with the best value (minimal). The problem is so complex to code it fully in Gurobi with constraints and objective function.
My question is: Could I apply the heuristic and the function inside a callback function with the parameters 'model' and 'where' in a way that Gurobi returns the best value considering this heuristic?
If the answer is Yes, do you have any example of code?
Many thanks.
-
Hi Ana,
technically applying your heuristic and function could be done from within a callback every time you get a feasible solution. But since the solver has no clue about the other function which you are trying to minimize, you would need to store your measures of quality someplace and then implement a routine to pick the best solution. Gurobi would have no information as to your measure of the quality of the solution, so - in this context - it would not be possible to have the solver tell you which of the solutions is the best.
But this would not be that much different to what you do now - instead of assessing all the solutions at once, you would assess them "on-the-fly". Perhaps this is useful though - maybe you could terminate early as soon as you find a solution which is "good enough"?
Alternatively, you could attempt to "include" the "heuristic" and the "function" in the model formulation. Then, the solver knows which solutions are "good" and which are "bad", and will definitely not return solutions which would be discarded by the "heuristic".
If you need a code example for the first option - let me know.
Hope this helps.
Best regards
Jonasz1 -
Many thanks, Jonasz, that is what I thought and the reason to ask here. Yes, please, send me a code example for the first option, only to know if I can improve something or, as you said, maybe with a good enough solution is enough for us.
The next step will be to formulate the overall problem, but we think that it considerably will improve the complexity (and the solution time for sure)
I look forward to receiving the code example.
Best,
Ana
0 -
A trivial code example would be:
import gurobipy as gp
def mycallback(model, where):
if where == GRB.Callback.MIPSOL
solution = model.cbGetSolution(model._vars)
model._solutions[model._solution_count] = solution
# perform your heuristic and quality check. I assume it's stored in variable `quality'
model._solutions_quality[model._solution_count] = quality
# You can also check here if the solution is good enough.
# I don't know how you measure quality, so I leave this out.
# If you are happy with the quality you get, you can use model.terminate() to terminate.
model._solution_count += 1
m = gp.Model()
# define your model here
m._solution_count = 0
m._solutions = {}
m._solutions_quality = {}
m._vars = m.getVars()
# ...
m.optimize(mycallback)Hope this makes sense. I have no way of testing this code now, so please treat it as rough guidance.
Best regards
Jonasz0 -
Thanks, Jonasz!
I have a doubt. The value of solution on the above code ( or print(model.cbGetSolution(model._vars))) is always an empty list. Could it be because I have no objective function to optimize? How should I proceed in this case?
Many thanks again!
0 -
If I write an objective function, the behaviour is still the same. I write a simplified version of the code. In my case, there may be hundreds of solutions with the same objective function so I want to use the heuristic inside the callback to select the best one. I don't know where the error is and why I get an empty list, so I can not treat the solution.
def mycallback(model, where):
if where == GRB.Callback.MIPSOL:
print(model.cbGetSolution(model._vars))
solution = model.cbGetSolution(model._vars)
model._solutions[model._solution_count] = solution
# perform your heuristic and quality check. I assume it's stored in variable `quality'
# As solution is an empty list, I comment the following lines
#model._solutions_quality[model._solution_count] = quality
# You can also check here if the solution is good enough.
# I don't know how you measure quality, so I leave this out.
# If you are happy with the quality you get, you can use model.terminate() to terminate.
model._solution_count += 1
m = Model() # Gurobi model# Parameters
# Gurobi variables
P = m.addVars(I,I,vtype=GRB.BINARY, name="Prio_")
# constraints...
# objective function
m.setObjective( quicksum(P[i,j] for i in I for j in I), GRB.MAXIMIZE )m.Params.Threads = 1
#With or without the following 2 lines, the result is the same
m.setParam('PoolSearchMode',2)
m.setParam('PoolSolutions',10) #m._solution_count = 0
m._solutions = {}
m._solutions_quality = {}
m._vars = m.getVars()m.optimize(mycallback)
This is the output:
Set parameter Username
Academic license - for non-commercial use only - expires 2023-09-24
Set parameter Threads to value 1
Set parameter TimeLimit to value 500
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64)
Thread count: 6 physical cores, 6 logical processors, using up to 1 threads
Optimize a model with 199 rows, 81 columns and 493 nonzeros
Model fingerprint: 0x665c8cbc
Variable types: 0 continuous, 81 integer (81 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 1e+00]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 1e+01]
[ ] (this is the result of print(model.cbGetSolution(model._vars)))
Found heuristic solution: objective 16.0000000
Presolve removed 179 rows and 71 columns
Presolve time: 0.00s
Presolved: 20 rows, 10 columns, 60 nonzeros
Variable types: 0 continuous, 10 integer (10 binary)Explored 0 nodes (0 simplex iterations) in 0.00 seconds (0.00 work units)
Thread count was 1 (of 6 available processors)Solution count 1: 16
Optimal solution found (tolerance 1.00e-04)
Best objective 1.600000000000e+01, best bound 1.600000000000e+01, gap 0.0000%User-callback calls 209, time in user-callback 0.00 sec
0
Please sign in to leave a comment.
Comments
5 comments