How does 'PoolSearchMode=1' works in a MIP problem? (using JuMP from Julia)
Answered
As mentioned, I want to find all possible solutions that satisfy some linear constraints. More specifically, I want to get a random choice in all these solutions. I then found that setting a `PoolSearchMode` can return multiple solutions as explained in the docs:
With a non-default value (
PoolSearchMode=1orPoolSearchMode=2), the MIP solver will try to findnsolutions, wherenis determined by the value of the PoolSolutions parameter. With a setting of 1, there are no guarantees about the quality of the extra solutions, while with a setting of 2, the solver will find thenbest solutions. The cost of the solve will increase with increasing values of this parameter.
I tried out the following code in Julia:
using Gurobi, JuMP
model = Model(Gurobi.Optimizer)
set_attribute(model, "PoolSearchMode", 1)
set_attribute(model, "PoolSolutions", 3)
@variable(model, x >= 0, Int)
@variable(model, 0<= y <= 3, Int)
@objective(model, Max, x-y)
@constraint(model, x+y<=10)
optimize!(model)
solutions = map(1:result_count(model)) do i
return (
x = value(x; result = i),
y = value(y; result = i),
obj = objective_value(model; result = i),
)
end
- How does Gurobi get an extra solution in a `PoolSearchMode` of 1? Can I consider the solution set `S_no_gurantee` as an unbiased sampling set from all solutions?
- When using the code from above, I still only get one solution in a `PoolSearchMode` of `. But if I set it to 2, I will get multiple solutions. Is there anything wrong with my code or how should I properly use the `PoolSearchMode` of 1?
-
Hi Jizhou Lu,
The non-systematic behaviour with PoolSearchMode =1 comes from the fact that the set of solutions found by the solver depends on the exact path the solver takes through the MIP search. The path of the solver can change due to various reasons, for example, variation in parameter settings.
The presolve reductions done on the model during the solve can impact the number of solutions found by the solver when using PoolSearchModel =1 or 2.
For your example, presolve will remove all variables and constraints, resulting in only one solution being returned when using PoolSearchMode=1. However, with PoolSearchMode=2, some presolve reductions are disabled, and the solver can find the "n" best solutions, where n is given by the PoolSolutions parameter.
If more solutions are desired when using PoolSearchMode=1, one option is to disable dual reductions in the model by setting DualReductions=0.
Regards,
Simran
1 -
Hi Simranjit Kaur,
I tried your suggestion and found that my model works similarly to a "PoolSearchMode" of 2, which get n best solutions. Is it possible for the model to get random extra solutions?
Best,
Jizhou Lu
0 -
Hi Jizhou Lu,
Let me first touch on how the solution pool is populated and updated during the optimization process.
Gurobi will keep adding solutions to the solution pool until it reaches the maximal pool size defined by the PoolSolutions parameter. If a new solution with a better objective value is found after the pool is full, the worst solution in the solution pool is discarded, and the new one is added.
Now, if the model is solved to optimality with PoolSearchMode = 1 and the solver finds the same set of solutions as with PoolsearchMode=2, then the solution pool with PoolSearchMode=1 will contain the same set of solutions as PoolSearchMode=2.
I can’t think of a straightforward way to add “random extra solutions” to the solution pool. You can try to get a high number of solutions in your solution pool and randomly choose one from them. Please note that retrieving a high number of solutions can make the optimization solve computationally expensive as the solver may need to spend extra effort in finding the required number of solutions.
Regards,
Simran
0
Please sign in to leave a comment.
Comments
3 comments