GNU Linear Programming Kit
The GNU Linear Programming Kit (GLPK) is a free software package designed for solving large-scale linear programming (LP), mixed integer programming (MIP), and related mathematical optimization problems.[1] Written in the ANSI C programming language, it provides a callable library of routines that can be integrated into custom applications or used via the standalone solver glpsol.[1] GLPK supports modeling in GNU MathProg, a subset of the AMPL language, allowing users to define variables, constraints, and objectives in a declarative format.[1]
Developed by Andrew Makhorin of the Moscow Aviation Institute starting in 2000, GLPK was registered as a GNU project in 2001 and has been maintained under the GNU General Public License version 3 or later.[1][2] The package implements established algorithms such as the primal and dual simplex methods for LP, interior-point methods, and branch-and-bound with branch-and-cut techniques for MIP problems.[3] It is particularly valued for its efficiency in handling problems with thousands of variables and constraints, making it suitable for applications in operations research, logistics, and resource allocation across industries.[3]
The latest stable release, version 5.0, was issued in December 2020, with ongoing support through the GNU mailing lists and community contributions.[4] GLPK's open-source nature has facilitated its integration into various tools, including interfaces for R, Python, and MATLAB, enhancing its accessibility for both research and practical optimization tasks.[1]
Introduction
Overview
The GNU Linear Programming Kit (GLPK) is a software package consisting of a set of routines written in the ANSI C programming language, organized as a callable library designed for solving large-scale linear programming (LP), mixed integer programming (MIP), and related mathematical optimization problems.[1][2] It enables developers to integrate optimization capabilities directly into applications, supporting problems with up to millions of variables and constraints, making it suitable for computationally intensive tasks in operations research and related fields.[1] The latest stable release is version 5.0, issued in December 2020.[5]
Key components of GLPK include a standalone driver program called glpsol, which allows users to solve models from the command line without embedding the library in custom code. Additionally, it provides the GNU MathProg modeling language, a subset of the AMPL (A Mathematical Programming Language) that facilitates declarative specification of optimization models in a concise, algebraic syntax.[1]
As part of the GNU Project, GLPK contributes to the development of free software tools for mathematical optimization, emphasizing portability across various platforms due to its ANSI C implementation. It is maintained by Andrew Makhorin.[1][2]
Licensing
The GNU Linear Programming Kit (GLPK) is distributed under the GNU General Public License (GPL) version 3 or later, as part of the GNU Project.[2] This license ensures that GLPK remains free software, allowing users worldwide to run, study, share, and modify the program without restrictions on the number of users or installations.
Copyright for GLPK was originally held by Andrew O. Makhorin, but was transferred to the Free Software Foundation in 2020 with the release of version 5.0, with all contributions licensed under the same GPL terms to maintain compatibility and openness.[1][5] The GPL grants permissions for free redistribution in source or binary form, modification of the software, and its use within both free and proprietary applications, provided that any derivative works distributed to others include the source code and adhere to the copyleft requirements of the GPL. This copyleft mechanism promotes collaborative development while preventing the software from being incorporated into closed-source products without disclosure.
Like all GPL-licensed software, GLPK is provided without any warranties, express or implied, including but not limited to merchantability or fitness for a particular purpose; users assume all risk associated with its use. In contrast to proprietary solvers such as IBM ILOG CPLEX, which require paid subscriptions for full-featured commercial use, typically starting from several thousand dollars annually, GLPK offers cost-free availability with no limits on problem size, making advanced linear programming capabilities accessible to academic, research, and non-commercial users without licensing fees.[6]
History and Development
Origins
The GNU Linear Programming Kit (GLPK) originated in 2000 when Andrew O. Makhorin, a researcher at the Moscow Aviation Institute's Department for Applied Informatics, initiated its development as a free alternative to proprietary linear programming solvers that dominated the field.[1][7] At the time, commercial tools like CPLEX and XPRESS were the primary options for solving large-scale optimization problems, limiting accessibility for academic and research users due to licensing costs and restrictions.[8]
Makhorin's background in operations research, combined with his involvement in the GNU Project, motivated the creation of GLPK to fill the gap in open-source software for linear and mixed-integer programming.[1] The primary goals were to provide a portable, C-based library capable of handling substantial optimization tasks in academia and research environments, where the absence of robust free tools hindered experimentation and education.[8] This effort aligned with the GNU Project's ethos of developing freely available software for mathematical and scientific computing.
The first public release of GLPK version 1.0 came in 2000, placed under the GNU General Public License and integrated into the GNU ecosystem, establishing it as an early open-source contender in operations research tooling.[1] This initial version focused on core functionality for linear programming, setting the foundation for subsequent enhancements while emphasizing portability across platforms.[9]
Major Releases
The GNU Linear Programming Kit (GLPK) began with its initial release, version 1.0, in October 2000, introducing a basic library for solving linear programming (LP) problems using the revised simplex method.[10] This foundational version established GLPK as a callable ANSI C library for large-scale LP optimization, with early distributions available via GNU FTP mirrors.[11]
Subsequent early releases expanded core capabilities. Version 2.0, released on January 25, 2001, added a tentative implementation of the primal-dual interior point method, providing an alternative to the simplex approach for improved numerical stability in certain LP instances.[12] Version 2.2, released on March 15, 2001, introduced branch-and-bound support for mixed integer programming (MIP) problems, enabling GLPK to handle integer constraints via a dual simplex-based procedure.[13] These updates marked GLPK's official integration into the GNU project, with version 2.0 coinciding with its formal acceptance as GNU software.[1]
| Version | Release Date | Key Improvements |
|---|
| 4.0 | May 6, 2003 | Introduced the GNU MathProg modeling language (a subset of AMPL) and the GLPSOL solver tool; discontinued the older GLPK/L language in favor of MathProg for enhanced model specification and documentation.[14] |
| 4.52 | July 18, 2013 | Reimplemented the clique cut generator for better handling of large and dense conflict graphs in MIP; added a simple rounding heuristic to the MIP optimizer and a new GLPSOL option for proximity search; fixed bugs in heuristics and MPS reading.[15] |
| 4.65 | February 16, 2018 | Added new API routines for LP/MIP preprocessing (e.g., glp_npp_preprocess1 for problem reduction); improved MIP solver with robust simple cover cuts; enabled long-step dual simplex by default for faster convergence.[16] |
| 5.0 | December 16, 2020 | Transferred copyright to the Free Software Foundation; disabled non-core routines (e.g., network generators) due to licensing conflicts, replacing them with dummies without impacting main LP/MIP functionality; fixed minor bugs for stability.[5] |
Technical Components
Core Library
The GNU Linear Programming Kit (GLPK) core library is implemented as a set of routines written in the ANSI C programming language, organized into modules that handle problem representation, solution processes, and control mechanisms. This callable library forms the foundational component of GLPK, enabling developers to integrate linear programming (LP) and mixed-integer programming (MIP) capabilities directly into C applications without external dependencies beyond a standard C compiler. The modular design separates concerns such as data structure management, matrix operations, and solver invocation, promoting reusability and maintainability.[9][1]
At the heart of the library are key data structures for representing optimization problems. The primary structure is the glp_prob object, which encapsulates an entire LP or MIP instance, including rows (auxiliary variables for constraints), columns (structural variables), and associated attributes like names, types, bounds, and scale factors. Constraints are formulated in the standard matrix form Ax = b, where the matrix A is stored in a sparse format for efficiency, accessible both row-wise and column-wise to support large-scale problems. Variable types include continuous (GLP_CV), integer (GLP_IV), and binary (GLP_BV), with bounds that can be free, lower-bounded, upper-bounded, double-bounded, or fixed. The objective function is also integrated into the glp_prob structure, specifying coefficients and direction (minimization or maximization).[9]
The application programming interface (API) provides functions for constructing and manipulating problem objects. Model building routines include glp_add_rows and glp_add_cols to dynamically add constraints and variables, respectively, along with glp_set_row_bnds and glp_set_col_bnds for defining bounds, and glp_set_obj_coef for assigning objective coefficients. The constraint matrix can be populated using glp_load_matrix, which accepts sparse triplet data. For invoking solutions, high-level functions such as glp_simplex (for LP problems) and glp_intopt (for MIP problems) are available, returning status information upon completion. Problem instances are created via glp_create_prob and deleted with glp_delete_prob.[9]
Memory management is explicitly controlled by the user through library routines like glp_create_prob for allocation and glp_delete_prob for deallocation of glp_prob objects, ensuring deterministic resource usage in embedded or long-running applications. Additional utilities such as glp_malloc, glp_calloc, and glp_free support custom memory handling where needed. Error handling relies on GLP status codes returned by API functions, such as GLP_EBADB for invalid bases, GLP_EBOUND for improper bounds, GLP_ESING for singular matrices, and GLP_OPT indicating an optimal solution; a return value of 0 denotes success. These codes facilitate robust integration by allowing immediate detection and response to issues.[9]
GLPK's core library emphasizes portability, compiling on Unix-like systems, Windows, and even resource-constrained embedded environments using any ANSI-compliant C compiler, with no mandatory external libraries required for basic functionality. Build options, such as those provided by GNU Libtool, further enhance cross-platform compatibility by supporting static or shared linking.[9][1]
Solvers and Algorithms
The GNU Linear Programming Kit (GLPK) implements solvers for linear programming (LP) and mixed integer programming (MIP) problems, emphasizing exact arithmetic for reliable solutions. For LP problems, GLPK provides the revised simplex method in both primal and dual variants, which iteratively pivots to find optimal basic feasible solutions through tableau updates. This method, invoked via the glp_simplex routine, uses LU factorization for basis representation and supports pricing strategies such as steepest edge to select entering variables efficiently.[20] Additionally, an interior-point solver based on the primal-dual method with Mehrotra's predictor-corrector technique addresses large-scale sparse problems in polynomial time, transforming the LP into standard form and employing ordering algorithms like approximate minimum degree for matrix factorization.[20]
For MIP problems, GLPK employs a branch-and-bound framework augmented with cutting planes, implemented in the glp_intopt routine, which systematically explores the search tree by branching on integer variables and bounding subproblems based on relaxation solutions. Cutting planes include Gomory fractional cuts to eliminate fractional solutions and mixed integer rounding (MIR) cuts to strengthen the linear programming relaxation, with optional clique cuts for further tightening. A presolver preprocesses the model by tightening variable bounds through probing and eliminating redundant constraints, reducing problem size before optimization. Heuristics such as the Driebeck-Tomlin method generate feasible integer solutions during branching to accelerate convergence.[20]
GLPK optimizes linear objective functions of the form \max or \min \, \mathbf{c}^T \mathbf{x} subject to \mathbf{Ax} \leq \mathbf{b}, \mathbf{x} \geq \mathbf{0}, incorporating support for equality constraints and general bounds on variables. Problems are typically formulated in standard LP form as
\min \, \mathbf{c} \mathbf{x} \quad \text{subject to} \quad \mathbf{A} \mathbf{x} = \mathbf{b}, \quad \mathbf{l} \leq \mathbf{x} \leq \mathbf{u},
where \mathbf{A} is the constraint matrix, \mathbf{b} the right-hand side, and \mathbf{l}, \mathbf{u} the lower and upper bounds. In the simplex method, tableau updates occur via pivoting: selecting an entering variable based on reduced costs, determining the leaving variable through ratio tests, and updating the basis to maintain feasibility and optimality conditions for basic feasible solutions.[20]
Convergence in GLPK solvers relies on configurable tolerance parameters to handle numerical precision. For the simplex method, parameters include tol_bnd (default $10^{-[7](/page/+7)}) for bound feasibility, tol_dj (default $10^{-[7](/page/+7)}) for reduced costs, and tol_piv (default $10^{-9}) for pivot selection, ensuring termination when residuals fall below these thresholds. The interior-point method uses a similar tolerance like GLP_TM_EPS (around $10^{-9}) to skip small coefficients and verify duality gap closure. An exact arithmetic mode, leveraging the GNU Multiple Precision library, further refines solutions by avoiding floating-point errors.[20]
GLPK deliberately omits support for quadratic or nonlinear programming, concentrating instead on linear and mixed integer models solved via exact methods rather than approximation heuristics, which limits its applicability but ensures deterministic, verifiable results.[20]
Modeling and Interfaces
GNU MathProg Language
The GNU MathProg language is a high-level, declarative modeling language designed for formulating linear programming (LP) and mixed integer programming (MIP) problems within the GLPK package. It serves as a subset of the AMPL (A Mathematical Programming Language) syntax, drawing from the foundational work in AMPL by Fourer, Gay, and Kernighan, but tailored specifically for GLPK's solver capabilities.[21] Model descriptions in MathProg allow users to define optimization problems in a script-like format that separates the mathematical structure from specific data instances, promoting reusability and clarity.[21] This language enables the specification of sets, parameters, decision variables, objective functions, and constraints in a concise manner, making it accessible for operations research practitioners and software developers.[1]
Core elements of MathProg include declarations for sets, parameters, and variables, followed by constraints and an objective function. Sets define index domains, such as set I := 1..5;, while parameters hold numeric or symbolic data, for example, param cost{i in I};. Variables are declared with bounds and types, like var x{i in I} >= 0, [integer](/page/Integer); for non-negative integer decisions. Constraints use the subject to (or s.t.) keyword within blocks, specifying linear relations, such as:
s.t. supply{i in I}: sum{j in J} x[i,j] <= cost[i];
s.t. supply{i in I}: sum{j in J} x[i,j] <= cost[i];
The objective is defined via minimize or maximize statements, e.g., minimize total: sum{i in I, j in J} c[i,j] * x[i,j];, and the solve; statement invokes the solver. These elements support linear expressions only, ensuring compatibility with GLPK's LP and MIP algorithms.[21]
Data input is handled through embedded sections or separate files, with .mod files containing the model structure and .dat files providing instance-specific values. For example, a data section might read:
data;
set I := Plant1 Plant2;
param capacity := Plant1 100 Plant2 150;
end;
data;
set I := Plant1 Plant2;
param capacity := Plant1 100 Plant2 150;
end;
The glpsol utility processes these files by translating the MathProg model into GLPK's internal problem format for solving, as in the command glpsol --model model.mod --data data.dat --solve.[21]
MathProg includes extensions for parametric studies via POSIX shell integration, allowing loops and conditionals in scripts for sensitivity analysis, such as embedding for loops to vary parameters across runs. However, it lacks support for nonlinear expressions, restricting its use to linear and integer linear models. A classic example is the transportation problem, where sets represent sources (I) and destinations (J), variables x[i,j] denote shipments, supply constraints ensure sum{j in J} x[i,j] <= a[i] for each source i, demand constraints require sum{i in I} x[i,j] >= b[j] for each destination j, and the objective minimizes total shipping cost sum{i in I, j in J} c[i,j] * x[i,j]. This parsed model is then passed to GLPK's core library for optimization.[21]
Bindings and Wrappers
The GNU Linear Programming Kit (GLPK) lacks official built-in language bindings, relying instead on community-developed wrappers to facilitate integration with higher-level programming languages beyond its native C interface.[1] These wrappers generally expose the core GLPK API for defining linear programming (LP) and mixed-integer programming (MIP) models, setting parameters, and retrieving solutions, enabling developers to leverage GLPK's solvers without direct C programming.[22] While comprehensive, these bindings are maintained independently, which can lead to delays in incorporating updates from GLPK's core releases, such as version 5.0.[1]
For Python, prominent bindings include PyGLPK, a more idiomatic interface that simplifies model construction and optimization calls compared to raw C API interactions, and SWIG-generated options like swiglpk, which provide direct access to GLPK functions.[23] High-level modeling libraries such as PuLP further extend accessibility by using GLPK as an optional backend solver; PuLP handles abstract model definition in Python syntax and invokes GLPK via file-based interfaces for solving LP and MIP problems.[24] These Python wrappers support full API functionality, including simplex and interior-point methods, and are installed via package managers like pip (e.g., pip install pyglpk or pip install pulp), with compatibility ensured for GLPK 5.0 when the underlying library is present.[25]
Java developers utilize GLPK-Java, a binding generated via the Java Native Interface (JNI) that wraps the GLPK C library for seamless LP and MIP solving within Java applications.[26] It offers complete exposure of model-building routines and solver controls, installable through Maven dependencies or system packages (e.g., sudo apt-get install libglpk-java on Debian-based systems), and requires GLPK 4.65 or later, including version 5.0.[26]
In R, the Rglpk package serves as the primary interface, providing high-level functions to formulate and solve LP and MILP problems directly in R scripts while interfacing with the GLPK library.[27] It supports the full range of GLPK's optimization capabilities and is installed from CRAN (e.g., install.packages("Rglpk")), depending on the system GLPK installation (version 5.0 compatible via libglpk-dev).[27]
Julia's GLPK.jl wrapper integrates GLPK with the JuMP modeling ecosystem and MathOptInterface, allowing users to build and solve models using Julia's native syntax while accessing the complete C API, including callbacks for advanced control.[22] Installation occurs via Julia's package manager (using Pkg; Pkg.add("GLPK")), which bundles compatible GLPK binaries (supporting version 5.0).[22]
MATLAB users can employ MEX-based wrappers, such as the GLPKMEX generator, which compiles a standalone MEX file to solve LP and MILP problems as alternatives to built-in functions like linprog, without requiring additional toolboxes.[28] This interface exposes GLPK's API through a documented MATLAB wrapper function and is compatible across MATLAB releases, including integration with GLPK 5.0 on Windows, macOS, and Linux.[28]
For .NET environments, including C#, the glpk-cli binding uses SWIG to create a Common Language Infrastructure (CLI) interface, enabling LP and MIP solving with full API access via P/Invoke mechanisms.[29] It is compiled from source or integrated into .NET projects, supporting GLPK 5.0, though users must manage the underlying GLPK DLL.[29]
Overall, these bindings enhance GLPK's portability but receive no official maintenance from the GLPK project, potentially resulting in version mismatches or incomplete feature parity after core updates.[1]
Usage and Applications
The GNU Linear Programming Kit (GLPK) provides glpsol as its primary standalone command-line tool, enabling users to solve linear programming (LP) and mixed integer programming (MIP) problems directly from the terminal without embedding the library in custom software. This executable reads problem data in supported formats such as GNU MathProg, MPS, or CPLEX LP, applies GLPK's solvers, and outputs results to files or standard output, making it suitable for quick prototyping, batch processing, or verification of models on systems where GLPK is installed. Glpsol operates purely in a command-line interface (CLI) environment, with no graphical user interface (GUI) available, emphasizing simplicity and portability across Unix-like systems and Windows.
To invoke glpsol, users specify the input model and optional data files, along with solver directives. The basic syntax is glpsol [options], where common invocations include reading a model in GNU MathProg format, such as glpsol --math model.mod --data data.dat -o solution.sol. Here, --math (or equivalently --mathprog) indicates the use of the GNU MathProg modeling language for the model file, --data supplies separate data, and -o directs the solution to a file. Solver selection options allow customization: --simplex employs the revised simplex method (default for LP and MIP), --interior uses the interior-point method (LP only), and MIP problems are handled automatically if integer variables are declared, though --nomip relaxes them to continuous for LP treatment. Additional controls include --min or --max for objective direction, --presol to enable problem presolving for efficiency, and limits like --tmlim nnn for time (in seconds) or --memlim nnn for memory (in MB).
Output from glpsol includes the problem status (e.g., optimal, infeasible, or unbounded), objective value, and primal/dual variable values, with verbosity controlled via --log file for detailed solver logs. Results can be formatted as printable text (-o file for a human-readable summary) or plain text (--write file for structured data suitable for parsing), and for simplex solutions, --ranges file generates sensitivity analysis reports on shadow prices and reduced costs. Glpsol also supports data validation without solving via --check, which inspects model integrity, and format conversions (e.g., --wlp file to export as CPLEX LP).
A typical workflow involves preparing a model file (e.g., model.mod defining variables, constraints, and objective in MathProg syntax), an optional data file (data.dat for parameters), executing glpsol --math model.mod --data data.dat --simplex -o solution.sol, and then reviewing the .sol file for variable assignments and status. For instance, solving a sample LP might yield output indicating an optimal objective of 3.0 with variable values x1=2.0 and x2=1.0, confirming feasibility. This CLI approach facilitates standalone usage in scripts or pipelines, such as generating reports from batch solves, while relying on underlying solvers like simplex for core computations.
Integration in Software
The GNU Linear Programming Kit (GLPK) is widely employed in operations research applications, particularly for tasks involving scheduling and resource allocation, where its open-source nature facilitates integration into custom workflows without licensing costs.[30] For instance, it supports optimization in production planning and logistics, enabling efficient allocation of limited resources across competing demands. GLPK is integrated into established tools such as GAMS through the COIN-OR GAMSlinks interface, which allows seamless use of GLPK as a solver within GAMS models.[31] Similarly, it is bundled in SageMath for mathematical computing and in GNU Octave for numerical analysis, providing direct access to LP and MIP solvers in these environments.[32][33]
Practical integrations often leverage language-specific bindings to embed GLPK in scripting workflows. In Python, libraries like PuLP interface with GLPK to model and solve mixed-integer programs, such as the 0-1 knapsack problem, where binary variables represent item selection to maximize value under a weight constraint; a typical script defines the objective, adds constraints, and invokes GLPK to compute the optimal subset.[34] For R users, the Rglpk package enables optimization in statistical contexts, such as portfolio allocation or experimental design, by formulating linear models directly in R code and solving them via GLPK's simplex or interior-point methods.[35] In Julia, the GLPK.jl package, part of the JuMP ecosystem, enables similar optimization tasks, such as resource allocation models, by interfacing with GLPK's solvers.[22] These examples highlight GLPK's role in embedding optimization into data analysis pipelines.
Regarding performance, GLPK scales effectively to large-scale problems on modern hardware, handling instances with over one million constraints and variables in linear programming tasks through its revised simplex and interior-point solvers.[36] However, for very large mixed-integer programs, it is generally slower than commercial alternatives like Gurobi. In benchmarks on metabolic models, GLPK performs comparably to other open-source solvers like SCIP.[37]
To optimize GLPK's performance in integrated applications, practitioners recommend enabling the built-in presolver, which eliminates redundant variables and constraints to reduce problem size before solving, often cutting computation time by 20-50% on structured models. Additionally, tuning MIP-specific parameters, such as selecting the most appropriate branching strategy (e.g., pseudocost or most fractional), can improve solution quality and speed for integer-heavy problems, with empirical testing advised for instance-specific gains.[38] These practices, detailed in GLPK's documentation, ensure efficient embedding without extensive reconfiguration.