[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Help-glpk] glpk 4.9 release information
From: |
Andrew Makhorin |
Subject: |
[Help-glpk] glpk 4.9 release information |
Date: |
Tue, 17 Jan 2006 23:31:48 +0300 |
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
GLPK 4.9 -- Release Information
===============================
Release date: Jan 17, 2006
GLPK (GNU Linear Programming Kit) is intended for solving large-scale
linear programming (LP), mixed integer linear programming (MIP), and
other related problems. It is a set of routines written in ANSI C and
organized in the form of a callable library.
In this release:
An advanced MIP solver was implemented. It includes:
- - basic presolving technique (removing free, singleton and redundant
rows, improving bounds of columns, removing fixed columns, reducing
constraint coefficents);
- - generating cutting planes to improve LP relaxation (currently only
Gomory's mixed integer cuts are implemented);
- - using the branch-and-bound method to solve resultant MIP;
- - recovering solution of the original MIP.
The solver is available on API level via the routine lpx_intopt (see
the reference manual). It is similar to the routine lpx_integer,
however, does not require initial solution of LP relaxation.
The solver is also available in the command-line utility glpsol via two
options: --intopt (only presolving) and --cuts (assumes --intopt plus
generating cuts).
Note that efficiency of the MIP solver strongly depends on the internal
structure of the problem to be solved. For some hard instances it is
highly efficient, but for other instances it may be significantly worse
than the standard branch-and-bound.
For some comparative benchmarks see doc/bench1.txt.
Three built-in functions were added to GNU MathProg: sin, cos, and atan
(the latter allows one or two arguments).
Some bugs were fixed.
Several new examples in GNU MathProg were included: color.mod (graph
coloring problem), tsp.mod (traveling salesman problem), and pbn.mod
(paint-by-numbers puzzle).
See GLPK web page at <http://www.gnu.org/software/glpk/glpk.html>.
GLPK distribution can be ftp'ed from <ftp://ftp.gnu.org/gnu/glpk/> or
from some mirror ftp sites; see <http://www.gnu.org/order/ftp.html>.
MD5 check-sum is the following:
e1aecaf58adaaf155d178a95e46f8d77 *glpk-4.9.tar.gz
GLPK is also available as a Debian GNU/Linux package. See its web page
at <http://packages.debian.org/stable/math/glpk.html>.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (MingW32)
iD8DBQFDzVP70XvyMFmB6BgRAoD9AJ9W8QobrDcW0KSrudK8eVhgPuzWLQCfbINd
+YQgzZhxsf5Np9raf/DsxC4=
=nl+V
-----END PGP SIGNATURE-----
- [Help-glpk] glpk 4.9 release information,
Andrew Makhorin <=