[Help-glpk] Re: GLPK newbie questions

[Harley Mackenzie]

Some followup questions.

>>1. What is the current status of GLPK?
>>Is it production quality, work in progress, able to handle large
>> problems?
>Glpk is work in progress. The simplex-based solver is able to handle
>problems with up to 100,000 constraints as reported by some users. In
>particular, it successfully solves all instances from netlib (see the
>file bench.txt included in the distribution). The interior-point solver
>is not very robust (unable to handle dense columns, sometimes terminates
>due to numeric instability or slow convergence). The mip solver
>currently is based on branch-and-bound, so it is unable to solve hard or
>very large mip's. Probably 100-200 integer variables is its limit in
>many cases, however, sometimes it is able to solve larger problems (say,
>up to 1000 integer variables) that depends on properties of particular
>instances.

You have mentioned the IOS (Integer Optimization Suite), which replaces BCS in 
version 4.2. What is IOS and what are its implications?
Is there work in progress to increase capacity?

>>2. How does it compare with other LP codes such as lp_solve and CPLEX
>> in terms of speed, size of problem and reliability?
>I think that on very large-scale instances cplex 8.0 dual simplex is
>10-100 times faster than the glpk simplex solver and, of course, much
>more robust :+)
>On the other hand, in many cases glpk is faster and more robust than
>lp_solve 4.0 for pure lp's as well as mip's.
>You can find benchmarks for some lp and mip solvers (in particular,
>for cplex, glpk, lp_solve, and osl) on Hans Mittelmann's webpage at
><http://plato.asu.edu/bench.html>.

Unfortunately the permissions are not set correctly on this site to FTP 
download the benchmarks but I will try and contact the site.

>>3. Why is it licensed under GPL and not LGPL?
>It is a philosophical question. Glpk is a GNU package developed under
>the GNU GPL from the very beginning.

I note that lp_solve is LGPL and that may promote its use. Is dual licensing an 
option?

>>4. Is there a Perl module for interfacing to GPLK and, if not, would
>> there be other interest in my developing such a module?
>As far as I know nobody has attempted to develop a Perl module for
>glpk. If you would like to contribute such module, please do that.

There is an existing Math::LP module on the Perl CPAN site, but it is a very 
simple interface to LP's in general and not very useful. I think a 
Math::LP::GLPK would need to be closer to the GLPK user interface, but the 
structure of the API would lend itself to an object oriented interface to hide 
the C structures from the user.

>>Would this module be then able to licensed under the normal Perl
>> artistic license, as is the norm for Perl modules, or must it then
>> be GPL? It gets complicated doesnt it?
>The module must be GPL'ed only if it includes some (or all) components
>of the glpk package.

GPL is non-standard for most Perl modules but I could live with this. Dual 
licensing would solve the problem.

>>5. What are the parts of AMPL not implemented in MathProg?
>The subset of AMPL implemented in MathProg approximately corresponds
>to AMPL status in 1990, because it is mainly based on the paper
>"A Modeling Language for Mathematical Programming" by Robert Fourer
>et al. published in that year.

Is GNU MathProg used for any other applications or was it developed for GLPK?

Regards,

Harley
------------------------------------------------------------------
     Dr. Harley Mackenzie         ACN:   087 953 839
                                  ABN:   27 087 953 839
     HARD Software                Web:   www.hardsoftware.com
     207 Noble Street             Tel:   +61 3 5222 3435
     Newtown 3220, Australia      Email: address@hidden
------------------------------------------------------------------