# GPLK vs Gurobi speed on simple MIPs

**URL:** <https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383>\
**Category:** Optimization (Mathematical)\
**Tags:** question, jump\
**Created:** [September 28, 2020, 12:30am UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383 "2020-09-28T00:30:50Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![adow031](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adow031/32/16403_2.png) [@adow031](https://discourse.julialang.org/u/adow031)\
**Post date:** [September 28, 2020, 12:30am UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/1 "2020-09-28T00:30:50Z")

</div>

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:

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

```

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

```julia
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:

```julia
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:

```julia
@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.

```julia
 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.

---

<div class="post-metadata">

**Author:** ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)\
**Post date:** [September 28, 2020, 1:17pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/2 "2020-09-28T13:17:50Z")

</div>

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:

```julia
model = JuMP.direct_model(Gurobi.Optimizer(env))

```

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [September 28, 2020, 1:48pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/3 "2020-09-28T13:48:40Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![remi-garcia](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/remi-garcia/32/7125_2.png) [@remi-garcia](https://discourse.julialang.org/u/remi-garcia)\
**Post date:** [September 28, 2020, 1:49pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/4 "2020-09-28T13:49:00Z")

</div>

> [@mtanneau](#):
>
> (i) the GLPK wrapper is more efficient than the Gurobi one

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

```Julia
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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 28, 2020, 9:34pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/5 "2020-09-28T21:34:07Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![adow031](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adow031/32/16403_2.png) [@adow031](https://discourse.julialang.org/u/adow031)\
**Post date:** [September 28, 2020, 10:08pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/6 "2020-09-28T22:08:48Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 28, 2020, 10:29pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/7 "2020-09-28T22:29:53Z")

</div>

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:

```nohighlight
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

```julia
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.

---

<div class="post-metadata">

**Author:** ![adow031](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adow031/32/16403_2.png) [@adow031](https://discourse.julialang.org/u/adow031)\
**Post date:** [September 28, 2020, 10:49pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/8 "2020-09-28T22:49:44Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [September 28, 2020, 11:07pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/9 "2020-09-28T23:07:16Z")

</div>

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

```nohighlight
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](https://github.com/jump-dev/CPLEX.jl/pull/316#issuecomment-698681068)

---

<div class="post-metadata">

**Author:** ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)\
**Post date:** [September 29, 2020, 2:56am UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/10 "2020-09-29T02:56:53Z")

</div>

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](https://github.com/mtanneau/Linda.jl).

For sub-problems, I would just keep all models in memory and update the objective as needed, see an example [here](https://github.com/mtanneau/DER_experiments/blob/master/src/oracle.jl). (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.

---

<div class="post-metadata">

**Author:** ![adow031](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/adow031/32/16403_2.png) [@adow031](https://discourse.julialang.org/u/adow031)\
**Post date:** [September 29, 2020, 12:46pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/11 "2020-09-29T12:46:30Z")

</div>

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](https://github.com/reganbaucke/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.

---

<div class="post-metadata">

**Author:** ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)\
**Post date:** [September 29, 2020, 1:07pm UTC](https://discourse.julialang.org/t/gplk-vs-gurobi-speed-on-simple-mips/47383/12 "2020-09-29T13:07:21Z")

</div>

Gurobi has evolved to be more efficient on large, hard MIP problems, sometimes at the detriment of smaller, easier ones. 🤷‍♂️

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](https://github.com/atoptima/Coluna.jl)