GPLK vs Gurobi speed on simple MIPs

Specific Domains Optimization (Mathematical)
,
1

I’m needing to solve a large number of simple MIPs in succession, and I’m finding that GPLK is 2.5 times faster than Gurobi (with presolve disabled; presolve slows Gurobi further). Is this normal?

I know that for large/complex MIPs Gurobi outperforms GPLK; however, I never realised that the overhead was so large.

Here’s an example:

using JuMP, GLPK, Gurobi, Random
env = Gurobi.Env()

I’ve got a function that generates a number of knapsack problems, with a specified solver:

function test_speed(model_count::Int64, numitems::Int64, solver)
   Random.seed!(1)

   numinvest = 6;
   investcost = zeros(model_count,numinvest)
   for m in 1:model_count
      investcost[m,:] = ([1,1.8,3.5,6.8,13.5,25])*(1-((m-1)/(model_count*1.2)))/40
   end
   investvol = [1,2,4,8,16,32]

   itemvolume = rand(numitems)*2 + collect(range(4,22,length = numitems))
   itemvalue = rand(numitems)

   function model_maker(model_index)
      model = Model(solver)
      @variable(model, bag[1:numinvest], Bin)
      @variable(model, y[1:numitems], Bin)
      @objective(model, Min,
            sum(-itemvalue[i] * y[i] for i in 1:numitems)+
            sum(investcost[model_index,i] * bag[i] for i in  1:numinvest))
      @constraint(model ,sum( y[i]*itemvolume[i] for i in 1:numitems) <=
            sum(bag[i]*investvol[i] for i in 1:numinvest))
      model
   end

   [model_maker(m) for m in 1:model_count]
end

For example, let’s set the number of models to be 1000, and the number of items to be selected from to be 100. We then generate the models for Gurobi and GLPK:

m=1000
n=100
models_Gurobi=test_speed(m,n,
   optimizer_with_attributes(() -> Gurobi.Optimizer(env),
      "OutputFlag" => 0, "MIPGap" => 0.0, "Presolve" => 0)))

models_GPLK=test_speed(m,n,
   optimizer_with_attributes(GLPK.Optimizer,
      "msg_lev" => 0, "mip_gap" => 0.0))

Finally, I time how long each takes to solve all the models:

@time for sp in models_Gurobi
   optimize!(sp)
end

@time for sp in models_GPLK
   optimize!(sp)
end

Here’s the output. The first is for Gurobi, the second is for GLPK.

 5.455270 seconds (2.72 M allocations: 152.580 MiB, 11.94% gc time)
 1.873296 seconds (3.06 M allocations: 171.813 MiB)

I ran these a few times to check the results, and they were consistent. I also checked that the solvers were getting the same answers, and they were. I finally tested CPLEX, and it is ever slower than Gurobi. Is this typical behaviour?

Is GPLK really the best solver for small MIPs, or are there some additional settings that I should be using?

Thanks.

1 Like
2

Can’t be 100% sure without detailed timing, but it may be that (i) the GLPK wrapper is more efficient than the Gurobi one, or (ii) GLPK is indeed faster than Gurobi on these problems (though Gurobi had no presolve).

Note that, by default, model = Model(solver) will create a cached copy of the model, which is then passed to the solver at optimize!, which comes with some overhead.

You may use direct mode instead:

model = JuMP.direct_model(Gurobi.Optimizer(env))
1 Like
3

Your test is measuring how much time GLPK takes to solve the model, and how much time Gurobi takes to build and solve the model.

Gurobi is lazy, it does not build the model until needed. The only thing you do that forces it to build the model is solving it, therefore inside optimize! you are counting the building time too.

4

I tried to reproduce your example querying the solve_time (and confirm or disprove (i)) and obtained:

julia> function testGurobi()
           solving_time = 0;
           models_Gurobi=test_speed(m,n,
                 optimizer_with_attributes(() -> Gurobi.Optimizer(env),
                    "OutputFlag" => 0, "MIPGap" => 0.0, "Presolve" => 0))
           for sp in models_Gurobi
               optimize!(sp)
               solving_time += solve_time(sp)
           end
           println(solving_time)
       end
testGurobi (generic function with 1 method)

julia> function testGLPK()
           solving_time = 0;
           models_GLPK=test_speed(m,n,
                 optimizer_with_attributes(GLPK.Optimizer,
                    "msg_lev" => 0, "mip_gap" => 0.0))
           for sp in models_GLPK
               optimize!(sp)
               solving_time += solve_time(sp)
           end
           println(solving_time)
       end
testGLPK (generic function with 1 method)

julia> testGurobi()
2.8382508754730225

julia> testGurobi()
2.666825294494629

julia> testGLPK()
1.2462358474731445

julia> testGLPK()
1.2181751728057861

It seems that (ii) GLPK is indeed faster than Gurobi on these problems. Removing the Presolve parameter makes it worse.

2 Likes
5

The solve times on my machine for a single model are ~4ms for Gurobi and 1.5ms for GLPK.

I’ve often found that Gurobi is slower than CPLEX/GLPK on small models. This is because Gurobi does most of their performance benchmarking on “hard” MIP instances which take > 100 seconds to solve. In practice, no customer is complaining about a MIP taking an extra 2ms to solve.

1 Like
6

Thanks all for your comments.

I’m running a decomposition algorithm, so I’m solving 100,000s of these small MIPs, instead of a single MIP with 100,000s of binary variables, so the difference in solve time between GLPK and Gurobi really adds up. Given your answers, it seems that GPLK may be the best option for my problem.

Thanks.

7

If the only thing changing is the objective, you could solve a few in a loop, and provide the previous solution as a warm-start.

You could also try tuning the parameters. On my new Gurobi rewrite branch (] add Gurobi#od/rewrite), do:

grb = backend(model)
GRBtunemodel(grb)
GRBgettuneresult(grb, 0)
GRBwrite(grb, "tune.prm")

The file tune.prm will have the best settings that Gurobi found.

For me it was

MIPGap  0
NormAdjust  1
MIPFocus  2
Cuts  1
Aggregate  0
OutputFlag  0

But that didn’t make much of a difference: 3ms instead of 4ms, so still slower than 1.5ms.

8

Thanks.

Yes, I am just updating costs between solves. My understanding is that now we have to manually set the starting solution in order to warm-start a MIP in JuMP. I tried this a while ago, and I found that the overhead in this was significant, and slowed down the overall solution process.

I’ll take a look at those parameters. Do I have to checkout that new branch or can I just set them directly?

9

You can set them directly. If everything is still in memory, Gurobi should re-use the solution from the previous solve. Alternatively, you can go

set_start_value.(all_variables(model), value.(all_variables(model)))

However, if you’re fighting over ms, then this may slow it down.

I just merged the PR, so now it is ] add Gurobi#master. It may also be a bit faster.

However, master contains breaking changes if you are using any of the C API. Here’s the full story: https://github.com/jump-dev/CPLEX.jl/pull/316#issuecomment-698681068

1 Like
10

No longer about GLPK vs Gurobi, but since you mentioned you’re using a decomposition…

FYI, I implemented a column-generation code for Dantzig-Wolfe decomposition with >1000s of sub-problems (which seems to be your case). That code (the column-generation part) is here.

For sub-problems, I would just keep all models in memory and update the objective as needed, see an example here. (in that example, each sub-problem optimizes the electrical consumption of a house; typically no more than a few hundred variables). Performance was OK even though I was not using warm-start.

Finally, and you may already know this: if you’re doing a column-generation (or Benders decomposition) scheme, and you have 100,000 sub-problems, then partial pricing can really speed things up.
For instance, you may want to solve only 10% of the sub-problems at each iteration.

2 Likes
11

Thanks for that column-generation code reference.

We are building a package, based on Dantzig-Wolfe decoposition, for stochastic capacity expansion problems; it’s called JuDGE.jl. This has column generation with optional partial-pricing. We’re just finalizing a paper, with some benchmarks, and were finding that not only were we able to outperform the Gurobi deterministic equivalent MIP using the decomposition, the decomposition using GPLK performed best - hence my question.

12

Gurobi has evolved to be more efficient on large, hard MIP problems, sometimes at the detriment of smaller, easier ones. :man_shrugging:

Finally, another pointer: the team of Francois Vanderbeck in Bordeaux have been developing a branch-and-price-and cut framework too. https://github.com/atoptima/Coluna.jl

1 Like