run time for gurobi/cplex versus cbc

[George DeLendonck]

Hi All,

I am in the process of assessing the viability of writing automatic placement programs using integer programming. I wrote the model using pulp and everything was easy to do. Using integer programming/pulp allows for very fast development and simple models
compared to the traditional method I have been using so far. The only issue is run time with CBC. The results are good but the run time is sometime prohibitive. I was wondering if anybody has some feel for how much faster the commercial solvers are compared
to CBC.

George Delendonck
geo...@atrenta.com________________________________

NOTE: This message and its attachments are intended only for the individual or
entity to which it is addressed and may contain confidential information or
forward-looking statements regarding product development. Forward-looking
statements are subject to change at Atrenta's sole discretion and Atrenta will have
no liability for the delay or failure to deliver any product or feature mentioned in
such forward-looking statements.

[Shawn Helm]

Hi George,

Here is graph for a MIP speed comparison of different solvers.
http://scip.zib.de/images/2011_01_16.png

Shawn

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To post to this group, send email to pulp-or...@googlegroups.com.
To unsubscribe from this group, send email to pulp-or-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pulp-or-discuss?hl=en.

[Stuart Mitchell]

If you are not familiar with integer programming there may be some
techniques that you can apply in the formulation to speed things up.

If you wish, send an email (off list if you prefer) with a description
of your problem and the formulation you used and I can see if there is
anything that can be easily done to improve your formulation. Or
perhaps you are interested in a good feasible solution rather than
proving optimality, then often a solution is found quickly.

If you send me an LP file prob.writeLP() and I will solve it with
gurobi and tell you how long it took.

Stu

> --
> You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
> To post to this group, send email to pulp-or...@googlegroups.com.
> To unsubscribe from this group, send email to pulp-or-discu...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/pulp-or-discuss?hl=en.
>
>

--
Stuart Mitchell
PhD Engineering Science
Freelance Programmer and Optimisation Expert
www.stuartmitchell.com

[George DeLendonck]

Thank you very much Stu. I will send you the file. I can also send you the python file which can be run as stand alone. I coded the problem in a very straight forward and probably naïve manner but I am really happy with the ease of use of the tool (pulp). I will simplify the test a bit before I send it to you. Take care

George

[George DeLendonck]

Hi Stu,
I have attached the LPfile.

I will send you the source code next.
What this code does is placing and shaping blocks to fit into a given area. This is classic block placement problem. The placement took three minutes using CBC for 14 blocks.

The problem does not require optimum solution. A reasonable solution reasonably fast is more what I am looking for.

Take care

-----Original Message-----
From: pulp-or...@googlegroups.com [mailto:pulp-or...@googlegroups.com] On Behalf Of Stuart Mitchell
Sent: Thursday, June 23, 2011 5:28 PM
To: pulp-or...@googlegroups.com
Subject: Re: run time for gurobi/cplex versus cbc

[Stuart Mitchell]

half a second with gurobi

$ time gurobi_cl LPFile.lp

Gurobi Optimizer version 4.5.1 build 7817 (linux64)
Copyright (c) 2011, Gurobi Optimization, Inc.

Read LP format model from file LPFile.lp
Reading time = 0.02 seconds
(null): 1372 rows, 546 columns, 4802 nonzeros
Optimize a model with 1372 rows, 546 columns and 4802 nonzeros
Presolve removed 677 rows and 16 columns
Presolve time: 0.01s
Presolved: 695 rows, 530 columns, 2426 nonzeros
Variable types: 76 continuous, 454 integer (454 binary)
Found heuristic solution: objective 24094.000000
Found heuristic solution: objective 19821.000000

Root relaxation: objective 1.330000e+04, 235 iterations, 0.00 seconds

Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time

0 0 13300.0000 0 14 19821.0000 13300.0000 32.9% - 0s
H 0 0 13607.642857 13300.0000 2.26% - 0s
0 0 13300.0000 0 20 13607.6429 13300.0000 2.26% - 0s
0 0 13300.0000 0 8 13607.6429 13300.0000 2.26% - 0s
0 0 13300.0000 0 6 13607.6429 13300.0000 2.26% - 0s
H 0 0 13471.119048 13300.0000 1.27% - 0s
0 0 13300.0000 0 10 13471.1190 13300.0000 1.27% - 0s
0 0 13300.0000 0 10 13471.1190 13300.0000 1.27% - 0s
H 0 0 13464.452381 13300.0000 1.22% - 0s
0 0 13300.0000 0 8 13464.4524 13300.0000 1.22% - 0s
0 0 13300.0000 0 12 13464.4524 13300.0000 1.22% - 0s
0 0 13300.0000 0 8 13464.4524 13300.0000 1.22% - 0s
0 0 13300.0000 0 4 13464.4524 13300.0000 1.22% - 0s
0 0 13300.0000 0 4 13464.4524 13300.0000 1.22% - 0s
0 0 13300.0000 0 4 13464.4524 13300.0000 1.22% - 0s
0 6 13300.0000 0 4 13464.4524 13300.0000 1.22% - 0s
* 128 114 98 13457.269841 13300.0000 1.17% 5.7 0s
* 173 114 73 13453.000000 13300.0000 1.14% 5.0 0s
* 813 505 88 13410.384921 13300.0000 0.82% 6.3 0s
H 814 532 13408.311508 13300.0000 0.81% 6.3 0s
H 905 402 13343.571429 13300.0000 0.33% 6.6 0s
H 953 416 13333.833333 13300.0000 0.25% 7.3 0s
H 1188 301 13301.250000 13300.0000 0.01% 6.8 0s

Cutting planes:
Implied bound: 33
MIR: 11

Explored 1839 nodes (14863 simplex iterations) in 0.62 seconds
Thread count was 8 (of 8 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 1.330125000000e+04, best bound 1.330000000000e+04, gap 0.0094%

real 0m0.645s
user 0m3.030s
sys 0m0.510s

[George DeLendonck]

Thanks for doing this for me.
This run time is amazing. Is that with multiple processors?

This is very significant because it makes the integer programming approach very attractive especially with pulp.

Also how can I learn how to write more efficient models with integer programming? Is there anything I can read about it?

George

[Stuart Mitchell]

Solve is on my laptop Intel(R) Core(TM) i7 CPU Q 740 @ 1.73GHz
with 8GB ram

try http://mat.gsia.cmu.edu/orclass/integer/integer.html for a
tutorial on integer programming

Stu

[George DeLendonck]

Hi Shawn,

 

Thanks for the benchmark info.

 

 

 

 

From: pulp-or...@googlegroups.com [mailto:pulp-or...@googlegroups.com] On Behalf Of Shawn Helm
Sent: Thursday, June 23, 2011 1:03 PM
To: pulp-or...@googlegroups.com
Subject: Re: run time for gurobi/cplex versus cbc

 

Hi George,