[Help-glpk] Re: GLPK newbie questions

[Andrew Makhorin]

Thank you for your interest in glpk.

>I am new to this list and have a number of questions that I think
> should be part of FAQ for the the GLPK software, as I am sure these
> are obvious to regular readers of this list. Here goes:
>
>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.

>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 dont expect it to be faster than a code such as CPLEX with lots of
> development resources behind it, just how does it compare.

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

>3. Why is it licensed under GPL and not LGPL?
>
>I am aware of the current FSF push for libraries to be licensed under
> GPL as this encourages GPL software to be developed and provides an
> advantage for GPL software. However, I would have thought that a GPL
> license for an LP library serverely restricts its possible use as
> there are other commercial alternatives that can be used in its place
> and is thus competing with them for market share. Free as in "Freedom"
> in this case would mean LGPL not GPL, if my interpretation is correct
> that if I develop a program that links to GLPK my code then must be
> distributed under GPL, if and only if I distribute the code. Is dual
> GPL and LGPL (or some other FOSS license such as BSD) a possibility
> with the library?

It is a philosophical question. Glpk is a GNU package developed under
the GNU GPL from the very beginning.

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

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

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

Andrew Makhorin