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 input

Jizhou Lu

• April 25, 2023 16:53

Hello,

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)

As you can see, I basically used Gurobi to obtain all the solutions that comply with the constraints (using PoolSearchMode=1, DualReduction=0 or PoolSearchMode=2), and then random sample one solution from the solution pool. But in both cases, the algorithm will run really slowly if large combination problems are encountered. Is there any better way to solve the problem?

Related to

• MIP
• Solutions

0

• 

  Eli Towle

  Gurobi Staff

  • April 25, 2023 23:06

  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
• 

  Jizhou Lu

  • April 26, 2023 00:06
  • Edited

  

  

  

  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
• 

  Eli Towle

  Gurobi Staff

  • April 26, 2023 00:18

  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.