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)

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
Please sign in to leave a comment.
Comments
3 comments