What is the most efficient way to generate a random solution from all possible solutions that comply with some constraints in a MIP?
Awaiting user inputHello,
I am not very familiar with MIP and LP. I want to have a random sample from all possible solutions that satisfy some linear constraints. There is an example code using JuMP from Julia:
using Gurobi, JuMP
model = Model(Gurobi.Optimizer)
@variable(model, x >= 0, Int)
@variable(model, y >= 0, Int)
# @objective(model, Max, 0) # not required
@constraint(model, x+y<=10)
set_silent(model)
set_attribute(model, "PoolSearchMode", 1)
set_attribute(model, "PoolSolutions", GRB_MAXINT)
set_attribute(model, "DualReductions", 0)
# alternative
# set_attribute(model, "PoolSearchMode", 2)
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
random_sample = sample(soulutions)
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
I can't think of a better way to accomplish this task using a MIP. To ensure the solution is random, you need to first enumerate all solutions. In general, enumerating all solutions of a MIP is computationally expensive.
0 -
It doesn't have to be completely random but deviates from the optimal solution, if I have an objective function. In the above case, the model picks "n best solutions", which is too biased. Is it possible to address this issue?
0 -
I don't see a way to address this using solution pools. Could you solve the problem repeatedly, perturbing or randomizing the objective function at each iteration to obtain a set of solutions that optimize different objectives? Of course, this approach also does not offer any guarantees about the randomness of solutions.
0
Post is closed for comments.
Comments
4 comments