Re: [Help-glpk] 4.48 vs 4.47

[Patrik Dufresne]

I've wrote about this behaviour a while ago. Where GLPK 4.37 find a solution for a specific problem within ~4sec, newer version take longer. I just want to point out GLPK 4.51 is doing better! Still it's far from 3sec. See

GLPK Version	Iteration	Time used
4.37	6507	3.6 secs
4.38	6496	5.5 secs
4.39	23708	22.1 secs
4.40	23708	22.1 secs
4.41	23708	23.6 secs
4.42	45540	64.6 secs
4.43	45540	64.4 secs
4.44	45540	60.7 secs
4.45	45540	60.3 secs
4.46	45540	61.5 secs
4.47	45540	61.0 secs
4.51	38445	46.7 secs

All the outputs and the problem are available on my dropbox: https://www.dropbox.com/sh/ja2myngas5lorow/oUTkkFxW5N/glpk-438-vs439

--

Patrik Dufresne

On Sun, Apr 14, 2013 at 4:41 PM, Haroldo Gambini Santos <address@hidden> wrote:

Hi Patrick,

I wrote a CBC guide sometime ago, hope it helps.

Cheers,

Haroldo

On 04/14/2013 11:44 AM, Patrik Dufresne wrote:

Hi Haroldo,

I'm not very familiar with clp-cbc and I want to compare it's performance on multiple models. Would you mind providing me the command line you used to solve by problem using clp-cbc ?

Thanks 

Patrik Dufresne

On Wed, Apr 10, 2013 at 11:29 PM, Haroldo Santos <address@hidden> wrote:

This benchmark may help also:

http://plato.asu.edu/ftp/lpfree.html 

On Thu, Apr 11, 2013 at 12:25 AM, Haroldo Santos <address@hidden> wrote:

lp_solve is worse than GLPK

Besides CLP, the only high quality open source LP solver I know is SoPlex:
http://soplex.zib.de/

Cheers

On Wed, Apr 10, 2013 at 11:33 PM, Patrik Dufresne <address@hidden> wrote:

Hi Horoldo,

Sorry, I didn't want to send this email directly to you but to the GLPK list. Still, I'm glad you answered. It does change the perspective I have to solve this performance issue. I didn't evaluate other mip solvers outside GLPK. I'm then courious about the performance of other solvers like clp-cbc and lp_solve. Do you have other suggestion?

The reasons, I may not use clp-cbc is as follow:

1. I need java binding. Last time I check the java binding for coin-or was either absent, not working or incomprehensible.

2. I need it to work on windows. Coin-or projects doesn't provide binaries for most of their project and even less for windows platform. I don't want to get the trouble of compiling or cross-compiling for windows platform.

Thanks for your suggestion.

Patrik Dufresne

On Wed, Apr 10, 2013 at 9:52 PM, Haroldo Santos <address@hidden> wrote:

As an advise (writing not to the GLPK list): use CLP and CBC

https://projects.coin-or.org/Clp

Solving your model in CLP on my machine takes 1.8 seconds. CLP is faster, more stable and has more options. For MIPS CBC is also a lot more powerful than GLPK.

Unfortunately GLPK is slow and numerically unstable for lots of problems...

On Wed, Apr 10, 2013 at 10:46 PM, Patrik Dufresne <address@hidden> wrote:

Bump, any tough about this problem? If the order of the variables as an impact on the simplex algorithm, any recommendation to re-order the variables? Should I use a callback function or only reorder/move the variables in the matrix? Is it possible to re-order the variables with glpsol?

Patrik Dufresne

On Tue, Mar 12, 2013 at 8:40 PM, Haroldo Santos <address@hidden> wrote:

glp_read_lp can be one of the causes:
The order of the variables can affect the number of simplex iterations - the index of the variable can be used to break ties in selecting the next variable to enter the base.

But it appears that this is a more complex issue: the processing time increased more than one time (a lot) as new GLPK versions appeared...

On Tue, Mar 12, 2013 at 9:05 PM, Patrik Dufresne <address@hidden> wrote:

Hi,

May someone give me an explanation about why the same problem run with glpk 4.38 is faster then glpk 4.47 ?

GLPK Version	Iteration	Time used
4.37	6507	3.6 secs
4.38	6496	5.5 secs
4.39	23708	22.1 secs
4.40	23708	22.1 secs
4.41	23708	23.6 secs
4.42	45540	64.6 secs
4.43	45540	64.4 secs
4.44	45540	60.7 secs
4.45	45540	60.3 secs
4.46	45540	61.5 secs
4.47	45540	61.0 secs

Run with

./glpsol --intopt --fpump --cpxlp min-all-swappable-task1

See my dropbox for all the results and the problem file

https://www.dropbox.com/sh/ja2myngas5lorow/oUTkkFxW5N/glpk-438-vs439

Looking at the change log, the only related modification I see that may impact the number of iteration if the reimplementation of glp_read_lp(). Thanks for your comments.

Patrik Dufresne

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

--
=============================================================
Haroldo Gambini Santos
Computing Department
Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo

--
=============================================================
Haroldo Gambini Santos
Computing Department
Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo

--
=============================================================
Haroldo Gambini Santos
Computing Department
Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo

--
=============================================================
Haroldo Gambini Santos
Computing Department
Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: www.decom.ufop.br/haroldo