Multi-cut Benders decomposition?

Specific Domains Optimization (Mathematical)
1

I have coded a Benders decomposition with JuMP, but it is currently running too slow for my needs. I have a way to speed up the process theoretically by collecting several solutions from the solver at each iteration of my algorithm, in order to generate more cuts at each step.
I am using Gurobi, and I found two parameters that could help me: the PoolSearchMode parameter and the PoolSolutions parameter.
However, I have not found a way to change those parameters from JuMP and recover several solutions at a time. Is it possible and if it is, how can I do?

2

I have not found a way to change those parameters from JuMP

You can set parameters by passing keyword arguments as follows:
Model(with_optimizer(Gurobi.Optimizer, OutputFlag=0))

Unfortunately, there is no easy way to recover several solutions.

You can query attributes as follows:

model = JuMP.direct_model(Gurobi.Optimizer())
N = 3
@variable(model, x[1:N] >= 0, Int)
Gurobi.set_intattr!(model.inner, "SolutionNumber", 2)
xn = Gurobi.get_dblattrarry(model.inner, "Xn", 1, Gurobi.num_vars(model.inner))

But then you need to line up the columns in the Gurobi model with the JuMP variables.

columns = Dict(
    v => Gurobi.LQOI.get_column(model, JuMP.index(v))
    for v in JuMP.all_variables(model))

Then you could look up the solution as follows.

xN_col = xn[columns[x[N]]]

Note: I haven’t tested any of this so there might be typos, etc.

If you get something working, it would be a good addition to the wrapper. Or at least post back here so people can find it in future.

3

Thanks for your reply, it helped a lot.
I got something working, so here is a code that gets the nb_poolsol best solutions encountered during the branch and bound performed by Gurobi on a toy example:

# Parameters
nb_poolsol = 10 
Nb_var = 3

# Charging model and solving it
myModel = JuMP.direct_model(Gurobi.Optimizer(PoolSearchMode=2, PoolSolutions=nb_poolsol, SolutionNumber=0))
@variable(myModel, x[1:Nb_var] >= 0, Int)
@objective(myModel, Max, x[1] + x[2] + x[3])
@constraint(myModel, x[1] + x[2] - x[3] <= 8 )
@constraint(myModel, x[1] - x[2] - x[3] <= 10 )
@constraint(myModel, -x[1] + x[2] + x[3] <= 15 )
@constraint(myModel, x[1] + 2*x[2] + 3*x[3] <= 20 )
optimize!(myModel)

# Print the last nb_poolsol solutions
for i in 0:(nb_poolsol-1)
    setparam!(myModel.moi_backend.inner,"SolutionNumber", i)
    xn = Gurobi.get_dblattrarray(myModel.moi_backend.inner, "Xn", 1, Nb_var)
    xn_val = Gurobi.get_dblattr(myModel.moi_backend.inner, "PoolObjVal")
    print(xn)
    print(" -> ")
    println(xn_val)
end
4

Hello.

I also tried to find all feasible solutions for linear programming problem. Did you face with problem

%D0%A1%D0%BD%D0%B8%D0%BC%D0%BE%D0%BA
%D0%A1%D0%BD%D0%B8%D0%BC%D0%BE%D0%BA1090×278 13.4 KB
???

Because when I try to find all solutions, gurobi said that there are no any other solutions

5

Hello,

I am sorry, I never had this particular problem.
However, every time I got a problem in the query part of this code, the real issue was in the model or in the resolution, not in the query