GNU Linear Programming Kit
Encyclopedia
The GNU Linear Programming Kit (GLPK) is a software package
intended for solving large-scale linear programming
(LP), mixed integer 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
. The package is part of the GNU Project
and is released under the GNU General Public License
.
Problems can be modeled in the language GNU MathProg which shares many parts of the syntax with AMPL
and solved with standalone solver GLPSOL.
GLPK can also be used as a C
library.
GLPK uses the revised simplex method and the primal-dual interior point method
for non-integer problems and the branch-and-bound
algorithm together with Gomory's mixed integer cuts for (mixed) integer problems.
GLPK is supported in the free edition of the OptimJ
modeling system
An independent project http://glpk-java.sourceforge.net provides a Java
-based interface to GLPK (via JNI). This allows Java applications to call out to GLPK in a relatively transparent manner.
. The first public release was in October 2000.
Software package (installation)
In package management systems, which are commonly used with Linux-based operating systems, a package is a specific piece of software which the system can install and uninstall....
intended for solving large-scale linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
(LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in ANSI C
ANSI C
ANSI C refers to the family of successive standards published by the American National Standards Institute for the C programming language. Software developers writing in C are encouraged to conform to the standards, as doing so aids portability between compilers.-History and outlook:The first...
and organized in the form of a callable library
Library (computer science)
In computer science, a library is a collection of resources used to develop software. These may include pre-written code and subroutines, classes, values or type specifications....
. The package is part of the GNU Project
GNU Project
The GNU Project is a free software, mass collaboration project, announced on September 27, 1983, by Richard Stallman at MIT. It initiated GNU operating system development in January, 1984...
and is released under the GNU General Public License
GNU General Public License
The GNU General Public License is the most widely used free software license, originally written by Richard Stallman for the GNU Project....
.
Problems can be modeled in the language GNU MathProg which shares many parts of the syntax with AMPL
AMPL
AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
and solved with standalone solver GLPSOL.
GLPK can also be used as a C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
library.
GLPK uses the revised simplex method and the primal-dual interior point method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...
for non-integer problems and the branch-and-bound
Branch and bound
Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, especially in discrete and combinatorial optimization...
algorithm together with Gomory's mixed integer cuts for (mixed) integer problems.
GLPK is supported in the free edition of the OptimJ
OptimJ
OptimJ is an extension of the Java with language support for writing optimization models and abstractions for bulk data processing. OptimJ aims at providing a clear and concise algebraic notation for optimization modeling, removing compatibility barriers between optimization modeling and...
modeling system
An independent project http://glpk-java.sourceforge.net provides a Java
Java (Sun)
Java refers to several computer software products and specifications from Sun Microsystems, a subsidiary of Oracle Corporation, that together provide a system for developing application software and deploying it in a cross-platform environment...
-based interface to GLPK (via JNI). This allows Java applications to call out to GLPK in a relatively transparent manner.
History
GLPK was developed by Andrew O. Makhorin (Андрей Олегович Махорин) of the Moscow Aviation InstituteMoscow Aviation Institute
Moscow Aviation Institute is one of several major engineering higher education establishments in Moscow .Although the school is currently offering a wide range of majors and research...
. The first public release was in October 2000.
- Version 1.1.1 contained a library for a revised primal and dual simplex algorithm.
- Version 2.0 introduced an implementation of the primal-dual interior point method.
- Version 2.2 added branch and bound solving of mixed integer problems.
- Version 2.4 added a first implementation of the GLPK/L modeling language.
- Version 4.0 replaced GLPK/L by the GNU MathProg modeling language, which is a subset of the AMPLAMPLAMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and solving high-complexity problems for large-scale mathematical computation AMPL, an acronym for "A Mathematical Programming Language", is an algebraic modeling language for describing and...
modeling language.
External links
- GLPK official site
- GLPK Wikibook
- GLPK for Debian GNU/Linux
- GLPK Lab for Windows
- GLPK for Windows
- GUSEK (Windows IDE for the GLPK stand-alone solver)
- GLPK for Cygwin
- GLPK for Mac OS X
- GLPK Perl interface
- GLPK PythonPython (programming language)Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
interfaces: - glpk - An R package
- Glpk for Java - A Java binding for GLPK
- glpkerl - An Erlang binding for GLPK