[Help-glpk] Re: Questions about the GLPK Package

[Andrew Makhorin]

> ICF came across the GLPK package via recommendations from operations
> research analysts working within the Office of Integrated Analysis and
> Forecasting within the Energy Information Administration (EIA).  ICF
> is helping the EIA conduct a survey of solvers that can serve as
> cost-effective alternatives to solver engines such as DASH and CPLEX.
> Below, I #8217;ve listed several questions that I have about GLPK.  If
> you can take a moment to answer them, I would greatly appreciate it.
> Thank you!

Thank you for your interest in glpk.

The glpk package is part of the GNU project, released under the aegis
of GNU. It is free software distributed under the GNU General Public
License v3. For more details please see:

http://www.gnu.org/software/glpk/
http://www.gnu.org/philosophy/free-sw.html
http://www.gnu.org/licenses/gpl.html

The glpk package includes the following main components:

* primal and dual simplex methods
* primal-dual interior-point method
* branch-and-cut method
* translator for GNU MathProg
* application program interface (API)
* stand-alone LP/MIP solver

Glpk supports the GNU MathProg modeling language, which is a subset of
the AMPL language.

Please note that the GLPK package is much less powerful than proprietary
packages like CPLEX and DASH. This means that hard and very large-scale
instances cannot be solved with glpk for a reasonable time.

> Software Requirements

> What are the input/output capabilities for the solver?  Does the
> solver have the capability for input/output files of the following
> formats: (a) delimited text (i.e. csv, etc); (b) structured text (i.e.
> xml, etc); (c) spreadsheets (i.e. xls, xlsx); (d) databases (i.e.
> Access databases); (e) proprietary format?  Does the solver support
> other database providers (e.g. Microsoft SQL Server, Oracle, MySQL, or
> PostgreSQL)?  What database drivers does the solver support? (e.g.
> native driver, OLE, ODBC)

The stand-alone solver glpsol supports three main formats: MPS format,
CPLEX LP format, and GLPK LP/MIP format.

The table feature implemented in the MathProg language allows reading
and writing data from/to external data tables. Currently the glpk table
drivers support CSV, DBF, ODBC and MySQL.

> Do external programs become integrated with the solver through: (a)
> static linkage; (b) dynamic linkage (i.e. DLL, shared objects, etc);
> (c) COM, DCOM, OLE; (d) RPC, network client-server, other or (e) all
> of the above, depending on the type of external program (If so, can
> you go into details?)?

Through static as well as dynamic linkage (.so on Linux machines, .dll
on Windows machines).

> Would the licensed user have access to the source code so as to alter
> capabilities of the solver to meet users #8217; needs?

Yes, because glpk is free software.

>  If not, what
> add-in capabilities are available to licensed users?

> How are upgrades made available to licensed users?

New glpk releases are distributed in the same way as any other GNU
packages. Please see http://www.gnu.org/prep/ftp.html .

> Would the solver
> provide them to licensed users for free for 1 year after purchase of a
> license?

See below.

> ICF is interested in learning more about how the solver outputs
> runtime debug information. For example, if one of ICF #8217;s
> programmers writes source code for a new model, how would he or she
> output runtime errors and warnings? Does the solver provide a function
> to output debug information to a text file, database, system log, etc,
> or some combination of multiple output mediums?

An incorrect call to glpk api routines causes an error message to be
sent to the terminal.

> What is the cost of a license per user?

The glpk package is free software and distributed gratis under GNU GPL.

> What are the operating system requirements for the solver?  (e.g.
> edition of Windows operating system, 32- or 64-bit? RAM required? Disk
> space required?)

Glpk is highly portable and can work on any modern 32- and 64-bit
platforms, including GNU/Linux and MS Windows. The amount of RAM
depends on the instance size. For small instances 1Mb of RAM is enough;
large or hard mip instances may require much more memory, because glpk
keeps all data in the RAM.

> With which programming language does the solver have an interface?
> What kind of interfaces are these? (e.g. interactive, object-oriented,
> etc)

The glpk package includes a callable library, which is intended to be
used in C or C++ application programs through glpk api. However, there
exist wrapper interface modules that allow using the glpk library from
other programming languages. See for example:
http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

> Calculation Requirements

> How many variables and constraints can the solver accommodate?  Can
> you provide your answer by type of problem?  (e.g. x and y number of
> variables and constrain for a linear and quadratic programming
> problem, respectively)

> Size limitations #8211; what are the size limitations of the model in
> terms of memory, and dimensions of arrays?

There is no special limit on the number of variables and constraints.

Please note that glpk does not support quadratic programming.

> Compare runs #8211; does the user interface allow the use of comparing
> runs

> What is the solver #8217;s graphing capability?  How many variables
> can be graphed against each other?  2?  3?  Can variables be compared
> against one another in a table format?

> What is the software #8217;s capability to create a customized
> template for displaying results via graphs and defining each variable
> on the graphs?

> Export Capabilities #8211; what are the solver #8217;s capabilities to
> export data to be graphed in another program (e.g. Excel)?  To export
> graphs into other programs?  To what programs can the data and graphs
> be exported?

> Does the user interface/graphic capability of the software allow the
> user to look at the model at an aggregated level, and then in more
> detail?  For instance, say the final result shows fuel consumption for
> all residential consumers in the US.  Would the interface/graphic
> capability show consumption of a particular type of fuel (e.g. natural
> gas, wind, or solar) for a particular state?

Glpk has no ide and does not support graphic capabilities. However, the
user can use Gusek (it is a separate development, not part of glpk).
For details please see: http://gusek.sourceforge.net/gusek.html .

> How does the solver read in data or the math programming language?

Data can be provided either in the data section, which is standard
feature of the MathProg modeling language, or in external data tables
(csv, dbf, etc.)

> How does it deal with data that have more than 2 dimensions?

The MathProg modeling langauge has standard features to deal with data
having two and more dimensions.

> Does the solver have the capability to solve linear programming, mixed
> integer programming, quadratic, and mixed integer quadratic
> programming problems?

Glpk supports only two problem classes: pure linear programming and
mixed-integer linear programming.

>  What are some of the solver #8217;s limitations
> and/or glitches when solving linear/mixed integer/quadratic/mixed
> integer quadratic programming problems?

Sometimes the glpk solvers may fail due to numerical instability or
excessive round-off errors.

> Can the solver just solve for individual components of the model, not
> the entire model, at any given time?

The glpsol stand-alone solver does not have such feature. However, it
is possible to do that using glpk api routines.

> Can different users use the optimizing engine to solve for different
> components of model simultaneously?

> Can you estimate the time for the optimizing engine to solve a model,
> based on the size of the model?

For some benchmarks please see:
http://lists.gnu.org/archive/html/help-glpk/2009-11/msg00066.html
http://lists.gnu.org/archive/html/help-glpk/2009-11/msg00013.html
http://lists.gnu.org/archive/html/help-glpk/2009-11/msg00017.html

> Because the Energy Information Administration #8217;s (EIA) National
> Energy Modeling System (NEMS) is considered public information, EIA
> must often make the source code, input files, and optimizing engine
> available to outside users.  How could the solver be made available
> through these outside users?  Is there a separate licensing term for
> them?

Please consult the GNU GPL license:
http://www.gnu.org/licenses/gpl.html

> Can other solvers be added to the DLL or other kinds of library in
> which solver engines are kept?  For instance, the EIA originally used
> a solver from KETRON.  Later, it decided that the DASH optimizing
> engine met some of its other needs.  KETRON customized its solver so
> that it can call DASH.  Does the solver have the capability for this
> kind of revision?  In what kinds of application programming language
> can the DLL or library be embedded?

Currently glpk does not allow using external solvers because of some
technical reasons. Probably this feature will appear in the future.

> ICF is currently dealing with input files that contain large
> multi-dimensional arrays with few non-zero entries.  How does the
> solver deal with sparse matrices? Would this method permit allocation
> of less memory to large sparse matrices?

All the glpk solvers use sparse formats.

> What are the solver #8217;s presolve and postsolve capabilities so as
> to make data more manageable?

Glpk has the lp/mip preprocessor which provides some standard features
like removing redundant rows, tightening column bounds, reducing
constraint coefficients, etc.

> What kinds of data management tools are used in the solver for
> generating matrices and reports, optimization control, and solution
> access?  How do they work with database and spreadsheet applications
> such as Access and Excel?  How do they work with text files?

In MathProg models it is possible to use the printf as well as table
statements to generate solution reoprts. However, exporting data to
spreadsheet applications is not supported.

> Can a user view a log that reports status of the model run during the
> optimization process? Could the status be made available after a
> certain number of iterations?  If so, how is this done?

By default the glpk solvers send some information about the solution
progress to the terminal and optionally to the log file. This output can
be either disabled or redirected.


Best regards,

Andrew Makhorin