alpar@9: alpar@9: GNU Linear Programming Kit FAQ alpar@9: alpar@9: Summary: Frequently Asked Questions about the GNU Linear Programming Kit alpar@9: alpar@9: Author: Dr. Harley Mackenzie alpar@9: alpar@9: Posting-Frequency: Monthly alpar@9: alpar@9: Language: English alpar@9: alpar@9: $Date: 2004/01/09 05:57:57 $ alpar@9: alpar@9: $Revision: 1.6 $ alpar@9: alpar@9: alpar@9: alpar@9: Introduction alpar@9: alpar@9: Q. What is GPLK? alpar@9: alpar@9: A. GLPK stands for the GNU Linear Programming Kit. The GLPK package is alpar@9: a set of routines written in ANSI C and organized in the form of a alpar@9: callable library. This package is intended for solving large-scale alpar@9: linear programming (LP), mixed integer linear programming (MIP), and alpar@9: other related problems. alpar@9: alpar@9: The GLPK package includes the following main components: alpar@9: alpar@9: * implementation of the simplex method, alpar@9: alpar@9: * implementation of the primal-dual interior point method, alpar@9: alpar@9: * implementation of the branch-and-bound method, alpar@9: alpar@9: * application program interface (API), alpar@9: alpar@9: * GNU MathProg modeling language (a subset of AMPL), alpar@9: alpar@9: * GLPSOL, a stand-alone LP/MIP solver. alpar@9: alpar@9: alpar@9: Q. Who develops and maintains GLPK? alpar@9: alpar@9: A. GLPK is currently developed and maintained by Andrew Makhorin, alpar@9: Department for Applied Informatics, Moscow Aviation Institute, Moscow, alpar@9: Russia. Andrew's email address is and his postal alpar@9: address is 125871, Russia, Moscow, Volokolamskoye sh., 4, Moscow alpar@9: Aviation Institute, Andrew O. Makhorin alpar@9: alpar@9: alpar@9: Q. How is GLPK licensed? alpar@9: alpar@9: A. GLPK is currently licensed under the GNU General Public License alpar@9: (GPL). GLPK is free software; you can redistribute it and/or modify it alpar@9: under the terms of the GNU General Public License as published by the alpar@9: Free Software Foundation; either version 2, or (at your option) any alpar@9: later version. alpar@9: alpar@9: GLPK is not licensed under the Lesser General Public License (LGPL) as alpar@9: distinct from other free LP codes such as lp_solve. The most alpar@9: significant implication is that code that is linked to the GLPK library alpar@9: must be released under the GPL, whereas with the LGPL, code linked to alpar@9: the library does not have to be released under the same license. alpar@9: alpar@9: alpar@9: Q. Where is the GLPK home page? alpar@9: alpar@9: The GLPK home page is part of the GNU web site and can found at alpar@9: . alpar@9: alpar@9: alpar@9: Q. How do I download and install GLPK? alpar@9: alpar@9: A. The GLPK source distribution can be found in the subdirectory alpar@9: /gnu/glpk/ on your favorite GNU mirror alpar@9: and can be compiled directly from alpar@9: the source. alpar@9: alpar@9: The GLPK package (like all other GNU software) is distributed in the alpar@9: form of packed archive. This is one file named 'glpk-x.y.tar.gz', where alpar@9: x is the major version number and y is the minor version number. alpar@9: alpar@9: In order to prepare the distribution for installation you should: alpar@9: alpar@9: 1. Copy the GLPK distribution file to some subdirectory. alpar@9: alpar@9: 2. Enter the command 'gzip -d glpk-x.y.tar.gz' in order to unpack the alpar@9: distribution file. After unpacking the name of the distribution file alpar@9: will be automatically changed to 'glpk-x.y.tar'. alpar@9: alpar@9: 3. Enter the command 'tar -x < glpk-x.y.tar' in order to unarchive the alpar@9: distribution. After this operation the subdirectory 'glpk-x.y' which is alpar@9: the GLPK distribution will have been automatically created. alpar@9: alpar@9: After you have unpacked and unarchived GLPK distribution you should alpar@9: configure the package, and compiled the application. The result of alpar@9: compilation is: alpar@9: alpar@9: * the file 'libglpk.a', which is a library archive containing object code alpar@9: for all GLPK routines; and alpar@9: alpar@9: * the program 'glpsol', which is a stand-alone LP/MIP solver. alpar@9: alpar@9: Complete compilation and installation instructions are included in the alpar@9: INSTALL file included with the distribution. alpar@9: alpar@9: The distribution includes make files for the Microsoft Visual C/C++ alpar@9: version 6 and Borland C/C++ version 5 and by default compiles and links alpar@9: a glpk*.lib library file, a glpk*.dll DLL file and an glpsol.exe alpar@9: application file. A GNU Windows 4.1 binary, source and documentation alpar@9: compiled using the mingw32 C/C++ compiler is also available from alpar@9: . alpar@9: alpar@9: alpar@9: Q. Is there a GLPK mailing list or newsgroup? alpar@9: alpar@9: A. GLPK has two mailing lists: and alpar@9: . alpar@9: alpar@9: The main discussion list is , and is used to discuss alpar@9: all aspects of GLPK, including its development and porting. There is alpar@9: also a special list used for reporting bugs at . alpar@9: alpar@9: To subscribe to any GLPK mailing list, send an empty mail with a alpar@9: Subject: header line of just "subscribe" to the relevant -request list. alpar@9: For example, to subscribe yourself to the main list, you would send alpar@9: mail to with no body and a Subject: header alpar@9: line of just "subscribe". alpar@9: alpar@9: Another way to subscribe to the GLP mailing lists is to visit the web alpar@9: pages and alpar@9: . alpar@9: alpar@9: Currently there are no newsgroups dedicated to GLPK. alpar@9: alpar@9: alpar@9: Q. Who maintains this FAQ and how do I contribute to this FAQ? alpar@9: alpar@9: A. The present maintainer of this FAQ is Dr. Harley Mackenzie, HARD alpar@9: software, although the content of the FAQ is derived from many sources alpar@9: such as GLPK documentation, GLPK email archives and original content. alpar@9: alpar@9: Harley's email address is and his postal address alpar@9: is c/o HARD software, PO Box 8004, Newtown, Victoria 3220, Australia. alpar@9: alpar@9: All contributions to this FAQ, such as questions and (preferably) alpar@9: answers should be sent to the email address. alpar@9: This FAQ is copyright Harley Mackenzie 2003 and is released under the alpar@9: same license, terms and conditions as GLPK, that is, GPL version 2 or alpar@9: later. alpar@9: alpar@9: Contributions are not directly referenced in the body of the FAQ as alpar@9: this would become unmanageable and messy, but rather as a list of alpar@9: contributors to this FAQ. If you are the author of any information alpar@9: included in this FAQ and you do not want your content to be included, alpar@9: please contact the FAQ maintainer and your material will be removed. alpar@9: Also if you have not been correctly included as a contributor to this alpar@9: FAQ, your details have changed, or you do not want your name listed in alpar@9: the list of contributors, please contact the FAQ maintainer for alpar@9: correction. alpar@9: alpar@9: alpar@9: Q. Where can I download this FAQ? alpar@9: alpar@9: The latest version of the GLPK FAQ is available to download from alpar@9: in the following alpar@9: formats: alpar@9: alpar@9: * DocBook alpar@9: alpar@9: * Formatted text alpar@9: alpar@9: * Adobe PDF alpar@9: alpar@9: alpar@9: Q. Who are the FAQ contributors? alpar@9: alpar@9: A. The FAQ contents were created from the following sources: alpar@9: alpar@9: * Michael Hennebry alpar@9: alpar@9: * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html alpar@9: alpar@9: * Harley Mackenzie, HARD software Pty. Ltd. alpar@9: alpar@9: * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation alpar@9: Institute alpar@9: alpar@9: alpar@9: GLPK functions & features alpar@9: alpar@9: Q. What is the current state of GLPK development? alpar@9: alpar@9: A. GLPK is a work in progress and is presently under continual alpar@9: development. As of the current version 4.3, GLPK is a simplex-based alpar@9: solver is able to handle problems with up to 100,000 constraints. In alpar@9: particular, it successfully solves all instances from netlib (see the alpar@9: file bench.txt included in the GLPK distribution). The interior-point alpar@9: solver is not very robust as it is unable to handle dense columns, alpar@9: sometimes terminates due to numeric instability or slow convergence. alpar@9: alpar@9: The Mixed Integer Programming (MIP) solver currently is based on alpar@9: branch-and-bound, so it is unable to solve hard or very large problems alpar@9: with a probable practical limit of 100-200 integer variables. However, alpar@9: sometimes it is able to solve larger problems of up to 1000 integer alpar@9: variables, although the size that depends on properties of particular alpar@9: problem. alpar@9: alpar@9: alpar@9: Q. How does GLPK compare with other LP codes? alpar@9: alpar@9: A. I think that on very large-scale instances CPLEX 8.0 dual simplex is alpar@9: 10-100 times faster than the GLPK simplex solver and, of course, much alpar@9: more robust. In many cases GLPK is faster and more robust than lp_solve alpar@9: 4.0 for pure LPs as well as MIP's. See the bench.txt file in the GLPK alpar@9: distribution doc directory for GLPK netlib benchmark results. alpar@9: alpar@9: You can find benchmarks for some LP and MIP solvers such as CPLEX, alpar@9: GLPK, lp_solve, and OSL on Hans Mittelmann's webpage at alpar@9: . alpar@9: alpar@9: alpar@9: Q. What are the differences between AMPL and GNU MathProg? alpar@9: alpar@9: A. The subset of AMPL implemented in MathProg approximately corresponds alpar@9: to AMPL status in 1990, because it is mainly based on the paper Robert alpar@9: Fourer, David M Gay and Brian W Kernighan (1990), "A Modeling Language alpar@9: for Mathematical Programming", Management Science, Vol 36, pp. 519-554 alpar@9: and is available at alpar@9: . alpar@9: alpar@9: The GNU MathProg translator was developed as part of GLPK. However, GNU alpar@9: MathProg can be easily used in other applications as there is a set of alpar@9: MathProg interface routines designed for use in other applications. alpar@9: alpar@9: alpar@9: Q. What input file formats does GLPK support? alpar@9: alpar@9: A. GLPK presently can read input and output LP model files in three alpar@9: supported formats: alpar@9: alpar@9: * MPS format - which is a column oriented and widely supported file alpar@9: format but has poor human readability. alpar@9: alpar@9: * CPLEX format - which is an easily readable row oriented format. alpar@9: alpar@9: * GNU MathProg - which is an AMPL like mathematical modeling language. alpar@9: alpar@9: alpar@9: Q. What interfaces are available for GLPK? alpar@9: alpar@9: A. The GLPK package is in fact a C API that can be either by statically alpar@9: or dynamically linked directly with many programming systems. alpar@9: alpar@9: Presently there are three contributed external interfaces included with alpar@9: the GLPK package: alpar@9: alpar@9: * GLPK Java Native Interface (JNI) alpar@9: alpar@9: * GLPK Delphi Interface (DELI) alpar@9: alpar@9: * GLPKMEX Matlab MEX interface alpar@9: alpar@9: There is an unofficial Microsoft Visual Basic, Tcl/Tk and Java GLPK alpar@9: interface available at alpar@9: . alpar@9: alpar@9: There are other language interfaces under development, including a Perl alpar@9: interface currently being developed by the FAQ maintainer, Dr. Harley alpar@9: Mackenzie . alpar@9: alpar@9: alpar@9: Q. Where can I find some examples? alpar@9: alpar@9: A. The GLPK package distribution contains many examples written in GNU alpar@9: MathProg (*.mod), C API calls (*.c), CPLEX input file format (*.lpt), alpar@9: MPS format (*.mps) as well as some specific Traveling Salesman examples alpar@9: (*.tsp). alpar@9: alpar@9: All of the examples can be found in the GLPK distribution examples alpar@9: sub-directory. alpar@9: alpar@9: alpar@9: Q. What are the future plans for GLPK? alpar@9: alpar@9: A. Developments planned for GLPK include improving the existing key alpar@9: GLPK components, such as developing a more robust and more efficient alpar@9: implementation of the simplex-based and interior-point solvers. Future alpar@9: GLPK enhancements planned are implementing a branch-and-cut solver, a alpar@9: MIP pre-processor, post-optimal and sensitivity analysis and possibly alpar@9: network simplex and quadratic programming solvers. alpar@9: alpar@9: alpar@9: Q. How do I report a GLPK bug? alpar@9: alpar@9: A. If you think you have found a bug in GLPK, then you should send as alpar@9: complete a report as possible to . alpar@9: alpar@9: alpar@9: Q. How do I contribute to the GLPK development? alpar@9: alpar@9: A. At present new GLPK development patches should be emailed to Andrew alpar@9: Makhorin , with sufficient documentation and test alpar@9: code to explain the nature of the patch, how to install it and the alpar@9: implications of its use. Before commencing any major GLPK development alpar@9: for inclusion in the GLPK distribution, it would be a good idea to alpar@9: discuss the idea on the GLPK mailing list. alpar@9: alpar@9: alpar@9: Q. How do I compile and link a GLPK application on a UNIX platform? alpar@9: alpar@9: A. To compile a GLPK application on a UNIX platform, then compiler must alpar@9: be able to include the GLPK include files and link to the GLPK library. alpar@9: For example, on a system where the GLPK system is installed: alpar@9: alpar@9: gcc mylp.c -o mylp -lglpk alpar@9: alpar@9: or specify the include files and libglpk.a explicitly, if GLPK is not alpar@9: installed. alpar@9: alpar@9: alpar@9: Q. How do I compile and link a GLPK application on a Win32 platform? alpar@9: alpar@9: A. On a Win32 platform, GLPK is implemented either as a Win32 Dynamic alpar@9: Link Library (DLL) or can be statically linked to the glpk*.lib file. alpar@9: As with the UNIX instructions, a GLPK application must set a path to alpar@9: the GLPK include files and also reference the GLPK library if alpar@9: statically linked. alpar@9: alpar@9: alpar@9: Q. How do I limit the GLPK execution time? alpar@9: alpar@9: A. You can limit the computing time by setting the control parameter alpar@9: LPX_K_TMLIM via the API routine lpx_set_real_parm . At present there is alpar@9: no way of limiting the execution time of glpsol without changing the alpar@9: source and recompiling a specific version. alpar@9: alpar@9: alpar@9: GLPK Linear Programming alpar@9: alpar@9: Q. What is Linear Programming and how does it work? alpar@9: alpar@9: A. Linear Programming is a mathematical technique that is a generic alpar@9: method for solving certain systems of equations with linear terms. The alpar@9: real power of LP's are that they have many practical applications and alpar@9: have proven to be a powerful and robust tool. alpar@9: alpar@9: The best single source of information on LP's is the Linear Programming alpar@9: FAQ alpar@9: alpar@9: that has information on LP's and MIP's, includes a comprehensive list alpar@9: of available LP software and has many LP references for further study. alpar@9: alpar@9: alpar@9: Q. How do I determine the stability of an LP solution? alpar@9: alpar@9: A. You can perform sensitivity analysis by specifying the --bounds alpar@9: option for glpsol as: alpar@9: alpar@9: glpsol ... --bounds filename alpar@9: alpar@9: in which case the solver writes results of the analysis to the alpar@9: specified filename in plain text format. The corresponding API routine alpar@9: is lpx_print_sens_bnds() . alpar@9: alpar@9: alpar@9: Q. How do I determine which constraints are causing infeasibility? alpar@9: alpar@9: A straightforward way to find such a set of constraints is to drop alpar@9: constraints one at a time. If dropping a constraint results in a alpar@9: solvable problem, pick it up and go on to the next constraint. After alpar@9: applying phase 1 to an infeasible problem, all basic satisfied alpar@9: constraints may be dropped. alpar@9: alpar@9: If the problem has a feasible dual, then running the dual simplex alpar@9: method is a more direct approach. After the last pivot, the nonbasic alpar@9: constraints and one of the violated constraints will constitute a alpar@9: minimal set. The GLPK simplex table routines will allow you to pick a alpar@9: correct constraint from the violated ones. alpar@9: alpar@9: Note that the GLPK pre-solver needs to be turned off for the preceding alpar@9: technique to work, otherwise GLPK does not keep the basis of an alpar@9: infeasible solution. alpar@9: alpar@9: Also a more detailed methodology has been posted on the mail list alpar@9: archive at alpar@9: . alpar@9: alpar@9: alpar@9: Q. What is the difference between checks and constraints? alpar@9: alpar@9: A. Check statements are intended to check that all data specified by alpar@9: the user of the model are correct, mainly in the data section of a alpar@9: MathProg model. For example, if some parameter means the number of alpar@9: nodes in a network, it must be positive integer, that is just the alpar@9: condition to be checked in the check statement (although in this case alpar@9: such condition may be also checked directly in the parameter alpar@9: statement). Note that check statements are performed when the alpar@9: translator is generating the model, so they cannot include variables. alpar@9: alpar@9: Constraints are conditions that are expressed in terms of variables and alpar@9: resolved by the solver after the model has been completely generated. alpar@9: If all data specified in the model are correct a priori, check alpar@9: statements are not needed and can be omitted, while constraints are alpar@9: essential components of the model and therefore cannot be omitted. alpar@9: alpar@9: alpar@9: GLPK Integer Programming alpar@9: alpar@9: Q. What is Integer Programming and how does it work? alpar@9: alpar@9: A. Integer LP models are ones whose variables are constrained to take alpar@9: integer or whole number (as opposed to fractional) values. It may not alpar@9: be obvious that integer programming is a very much harder problem than alpar@9: ordinary linear programming, but that is nonetheless the case, in both alpar@9: theory and practice. alpar@9: alpar@9: alpar@9: Q. What is the Integer Optimization Suite (IOS)? alpar@9: alpar@9: A. IOS is a framework to implement implicit enumeration methods based alpar@9: on LP relaxation (like branch-and-bound and branch-and-cut). Currently alpar@9: IOS includes only basic features (the enumeration tree, API routines, alpar@9: and the driver) and is not completely documented. alpar@9: alpar@9: alpar@9: Q. I have just changed an LP to a MIP and now it doesn't work? alpar@9: alpar@9: A. If you have an existing LP that is working and you change to an MIP alpar@9: and receive a "lpx_integer: optimal solution of LP relaxation required" alpar@9: 204 (==LPX_E_FAULT) error, you probably have not called the LP solution alpar@9: method lpx_simplex() before lpx_integer() . The MIP routines use the LP alpar@9: solution as part of the MIP solution methodology. alpar@9: