The GNU Linear Programming Kit (GLPK) is a software package intended for solving large-scale

linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

(LP), mixed integer programming (MIP), and other related problems. It is a set of routines written in

ANSI C ANSI C, ISO C, and Standard C are successive standards for the C programming language published by the American National Standards Institute (ANSI) and ISO/IEC JTC 1/SC 22/WG 14 of the International Organization for Standardization (ISO) and the ...

and organized in the form of a callable

library A library is a collection of Book, books, and possibly other Document, materials and Media (communication), media, that is accessible for use by its members and members of allied institutions. Libraries provide physical (hard copies) or electron ...

. The package is part of the

GNU Project The GNU Project ( ) is a free software, mass collaboration project announced by Richard Stallman on September 27, 1983. Its goal is to give computer users freedom and control in their use of their computers and Computer hardware, computing dev ...

and is released under the

GNU General Public License The GNU General Public Licenses (GNU GPL or simply GPL) are a series of widely used free software licenses, or ''copyleft'' licenses, that guarantee end users the freedom to run, study, share, or modify the software. The GPL was the first ...

. GLPK uses the revised simplex method and the primal-dual

interior point method Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving Linear programming, linear and nonlinear programming, non-linear convex optimization problems. IPMs combine two advantages of previously-known algorit ...

for non-integer problems and the

branch-and-bound Branch and bound (BB, B&B, or BnB) is a method for solving optimization problems by breaking them down into smaller sub-problems and using a bounding function to eliminate sub-problems that cannot contain the optimal solution. It is an algorithm ...

algorithm together with Gomory's mixed integer cuts for (mixed) integer problems.

History

GLPK was developed by Andrew O. Makhorin (Андрей Олегович Махорин) of the

Moscow Aviation Institute Moscow Aviation Institute () is an engineering research university in Moscow, Russia. It is designated a National Research University. Since its inception the institute has been spearheading advances in aerospace technology both within Russia a ...

. The first public release was in October 2000. * Version 1.1.1 contained a

for a revised primal and dual simplex algorithm. * Version 2.0 introduced an

implementation Implementation is the realization of an application, execution of a plan, idea, scientific modelling, model, design, specification, Standardization, standard, algorithm, policy, or the Management, administration or management of a process or Goal ...

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

AMPL AMPL (A Mathematical Programming Language) is an algebraic modeling language to describe and solve high-complexity problems for large-scale mathematical computing (e.g. large-scale optimization and scheduling-type problems). It was developed ...

modeling language A modeling language is any artificial language that can be used to express data, information or knowledge or systems in a structure that is defined by a consistent set of rules. The rules are used for interpretation of the meaning of components in ...

Interfaces and wrappers

Since version 4.0, GLPK problems can be modeled using GNU MathProg (GMPL), a subset of the

modeling language used only by GLPK. However, GLPK is most commonly called from other programming languages. Wrappers exist for: * Julia and the JuMP modeling package *

Java Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...

(using OptimJ)

References

External links

GLPK official site
* GLPK Wikibook {{Mathematical optimization software Linear Programming Kit Mathematical optimization software Free mathematics software Free software programmed in C Mathematics software for Linux

History

Interfaces and wrappers

Further reading

References

External links