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