1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/doc/glpk_faq.txt Mon Dec 06 13:09:21 2010 +0100
1.3 @@ -0,0 +1,435 @@
1.4 +
1.5 +GNU Linear Programming Kit FAQ
1.6 +
1.7 + Summary: Frequently Asked Questions about the GNU Linear Programming Kit
1.8 +
1.9 + Author: Dr. Harley Mackenzie <hjm@hardsoftware.com>
1.10 +
1.11 + Posting-Frequency: Monthly
1.12 +
1.13 + Language: English
1.14 +
1.15 + $Date: 2004/01/09 05:57:57 $
1.16 +
1.17 + $Revision: 1.6 $
1.18 +
1.19 +
1.20 +
1.21 +Introduction
1.22 +
1.23 + Q. What is GPLK?
1.24 +
1.25 + A. GLPK stands for the GNU Linear Programming Kit. The GLPK package is
1.26 + a set of routines written in ANSI C and organized in the form of a
1.27 + callable library. This package is intended for solving large-scale
1.28 + linear programming (LP), mixed integer linear programming (MIP), and
1.29 + other related problems.
1.30 +
1.31 + The GLPK package includes the following main components:
1.32 +
1.33 + * implementation of the simplex method,
1.34 +
1.35 + * implementation of the primal-dual interior point method,
1.36 +
1.37 + * implementation of the branch-and-bound method,
1.38 +
1.39 + * application program interface (API),
1.40 +
1.41 + * GNU MathProg modeling language (a subset of AMPL),
1.42 +
1.43 + * GLPSOL, a stand-alone LP/MIP solver.
1.44 +
1.45 +
1.46 + Q. Who develops and maintains GLPK?
1.47 +
1.48 + A. GLPK is currently developed and maintained by Andrew Makhorin,
1.49 + Department for Applied Informatics, Moscow Aviation Institute, Moscow,
1.50 + Russia. Andrew's email address is <mao@mai2.rcnet.ru> and his postal
1.51 + address is 125871, Russia, Moscow, Volokolamskoye sh., 4, Moscow
1.52 + Aviation Institute, Andrew O. Makhorin
1.53 +
1.54 +
1.55 + Q. How is GLPK licensed?
1.56 +
1.57 + A. GLPK is currently licensed under the GNU General Public License
1.58 + (GPL). GLPK is free software; you can redistribute it and/or modify it
1.59 + under the terms of the GNU General Public License as published by the
1.60 + Free Software Foundation; either version 2, or (at your option) any
1.61 + later version.
1.62 +
1.63 + GLPK is not licensed under the Lesser General Public License (LGPL) as
1.64 + distinct from other free LP codes such as lp_solve. The most
1.65 + significant implication is that code that is linked to the GLPK library
1.66 + must be released under the GPL, whereas with the LGPL, code linked to
1.67 + the library does not have to be released under the same license.
1.68 +
1.69 +
1.70 + Q. Where is the GLPK home page?
1.71 +
1.72 + The GLPK home page is part of the GNU web site and can found at
1.73 + <http://www.gnu.org/software/glpk/glpk.html>.
1.74 +
1.75 +
1.76 + Q. How do I download and install GLPK?
1.77 +
1.78 + A. The GLPK source distribution can be found in the subdirectory
1.79 + /gnu/glpk/ on your favorite GNU mirror
1.80 + <http://www.gnu.org/prep/ftp.html> and can be compiled directly from
1.81 + the source.
1.82 +
1.83 + The GLPK package (like all other GNU software) is distributed in the
1.84 + form of packed archive. This is one file named 'glpk-x.y.tar.gz', where
1.85 + x is the major version number and y is the minor version number.
1.86 +
1.87 + In order to prepare the distribution for installation you should:
1.88 +
1.89 + 1. Copy the GLPK distribution file to some subdirectory.
1.90 +
1.91 + 2. Enter the command 'gzip -d glpk-x.y.tar.gz' in order to unpack the
1.92 + distribution file. After unpacking the name of the distribution file
1.93 + will be automatically changed to 'glpk-x.y.tar'.
1.94 +
1.95 + 3. Enter the command 'tar -x < glpk-x.y.tar' in order to unarchive the
1.96 + distribution. After this operation the subdirectory 'glpk-x.y' which is
1.97 + the GLPK distribution will have been automatically created.
1.98 +
1.99 + After you have unpacked and unarchived GLPK distribution you should
1.100 + configure the package, and compiled the application. The result of
1.101 + compilation is:
1.102 +
1.103 + * the file 'libglpk.a', which is a library archive containing object code
1.104 + for all GLPK routines; and
1.105 +
1.106 + * the program 'glpsol', which is a stand-alone LP/MIP solver.
1.107 +
1.108 + Complete compilation and installation instructions are included in the
1.109 + INSTALL file included with the distribution.
1.110 +
1.111 + The distribution includes make files for the Microsoft Visual C/C++
1.112 + version 6 and Borland C/C++ version 5 and by default compiles and links
1.113 + a glpk*.lib library file, a glpk*.dll DLL file and an glpsol.exe
1.114 + application file. A GNU Windows 4.1 binary, source and documentation
1.115 + compiled using the mingw32 C/C++ compiler is also available from
1.116 + <http://gnuwin32.sourceforge.net/packages/glpk.htm>.
1.117 +
1.118 +
1.119 + Q. Is there a GLPK mailing list or newsgroup?
1.120 +
1.121 + A. GLPK has two mailing lists: <help-glpk@gnu.org> and
1.122 + <bug-glpk@gnu.org>.
1.123 +
1.124 + The main discussion list is <help-glpk@gnu.org>, and is used to discuss
1.125 + all aspects of GLPK, including its development and porting. There is
1.126 + also a special list used for reporting bugs at <bug-glpk@gnu.org>.
1.127 +
1.128 + To subscribe to any GLPK mailing list, send an empty mail with a
1.129 + Subject: header line of just "subscribe" to the relevant -request list.
1.130 + For example, to subscribe yourself to the main list, you would send
1.131 + mail to <help-glpk-request@gnu.org> with no body and a Subject: header
1.132 + line of just "subscribe".
1.133 +
1.134 + Another way to subscribe to the GLP mailing lists is to visit the web
1.135 + pages <http://mail.gnu.org/mailman/listinfo/help-glpk> and
1.136 + <http://mail.gnu.org/mailman/listinfo/bug-glpk>.
1.137 +
1.138 + Currently there are no newsgroups dedicated to GLPK.
1.139 +
1.140 +
1.141 + Q. Who maintains this FAQ and how do I contribute to this FAQ?
1.142 +
1.143 + A. The present maintainer of this FAQ is Dr. Harley Mackenzie, HARD
1.144 + software, although the content of the FAQ is derived from many sources
1.145 + such as GLPK documentation, GLPK email archives and original content.
1.146 +
1.147 + Harley's email address is <hjm@hardsoftware.com> and his postal address
1.148 + is c/o HARD software, PO Box 8004, Newtown, Victoria 3220, Australia.
1.149 +
1.150 + All contributions to this FAQ, such as questions and (preferably)
1.151 + answers should be sent to the <hjm@hardsoftware.com> email address.
1.152 + This FAQ is copyright Harley Mackenzie 2003 and is released under the
1.153 + same license, terms and conditions as GLPK, that is, GPL version 2 or
1.154 + later.
1.155 +
1.156 + Contributions are not directly referenced in the body of the FAQ as
1.157 + this would become unmanageable and messy, but rather as a list of
1.158 + contributors to this FAQ. If you are the author of any information
1.159 + included in this FAQ and you do not want your content to be included,
1.160 + please contact the FAQ maintainer and your material will be removed.
1.161 + Also if you have not been correctly included as a contributor to this
1.162 + FAQ, your details have changed, or you do not want your name listed in
1.163 + the list of contributors, please contact the FAQ maintainer for
1.164 + correction.
1.165 +
1.166 +
1.167 + Q. Where can I download this FAQ?
1.168 +
1.169 + The latest version of the GLPK FAQ is available to download from
1.170 + <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> in the following
1.171 + formats:
1.172 +
1.173 + * DocBook
1.174 +
1.175 + * Formatted text
1.176 +
1.177 + * Adobe PDF
1.178 +
1.179 +
1.180 + Q. Who are the FAQ contributors?
1.181 +
1.182 + A. The FAQ contents were created from the following sources:
1.183 +
1.184 + * Michael Hennebry
1.185 +
1.186 + * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
1.187 +
1.188 + * Harley Mackenzie, HARD software Pty. Ltd.
1.189 +
1.190 + * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation
1.191 + Institute
1.192 +
1.193 +
1.194 +GLPK functions & features
1.195 +
1.196 + Q. What is the current state of GLPK development?
1.197 +
1.198 + A. GLPK is a work in progress and is presently under continual
1.199 + development. As of the current version 4.3, GLPK is a simplex-based
1.200 + solver is able to handle problems with up to 100,000 constraints. In
1.201 + particular, it successfully solves all instances from netlib (see the
1.202 + file bench.txt included in the GLPK distribution). The interior-point
1.203 + solver is not very robust as it is unable to handle dense columns,
1.204 + sometimes terminates due to numeric instability or slow convergence.
1.205 +
1.206 + The Mixed Integer Programming (MIP) solver currently is based on
1.207 + branch-and-bound, so it is unable to solve hard or very large problems
1.208 + with a probable practical limit of 100-200 integer variables. However,
1.209 + sometimes it is able to solve larger problems of up to 1000 integer
1.210 + variables, although the size that depends on properties of particular
1.211 + problem.
1.212 +
1.213 +
1.214 + Q. How does GLPK compare with other LP codes?
1.215 +
1.216 + A. I think that on very large-scale instances CPLEX 8.0 dual simplex is
1.217 + 10-100 times faster than the GLPK simplex solver and, of course, much
1.218 + more robust. In many cases GLPK is faster and more robust than lp_solve
1.219 + 4.0 for pure LPs as well as MIP's. See the bench.txt file in the GLPK
1.220 + distribution doc directory for GLPK netlib benchmark results.
1.221 +
1.222 + You can find benchmarks for some LP and MIP solvers such as CPLEX,
1.223 + GLPK, lp_solve, and OSL on Hans Mittelmann's webpage at
1.224 + <http://plato.asu.edu/bench.html>.
1.225 +
1.226 +
1.227 + Q. What are the differences between AMPL and GNU MathProg?
1.228 +
1.229 + A. The subset of AMPL implemented in MathProg approximately corresponds
1.230 + to AMPL status in 1990, because it is mainly based on the paper Robert
1.231 + Fourer, David M Gay and Brian W Kernighan (1990), "A Modeling Language
1.232 + for Mathematical Programming", Management Science, Vol 36, pp. 519-554
1.233 + and is available at
1.234 + <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf>.
1.235 +
1.236 + The GNU MathProg translator was developed as part of GLPK. However, GNU
1.237 + MathProg can be easily used in other applications as there is a set of
1.238 + MathProg interface routines designed for use in other applications.
1.239 +
1.240 +
1.241 + Q. What input file formats does GLPK support?
1.242 +
1.243 + A. GLPK presently can read input and output LP model files in three
1.244 + supported formats:
1.245 +
1.246 + * MPS format - which is a column oriented and widely supported file
1.247 + format but has poor human readability.
1.248 +
1.249 + * CPLEX format - which is an easily readable row oriented format.
1.250 +
1.251 + * GNU MathProg - which is an AMPL like mathematical modeling language.
1.252 +
1.253 +
1.254 + Q. What interfaces are available for GLPK?
1.255 +
1.256 + A. The GLPK package is in fact a C API that can be either by statically
1.257 + or dynamically linked directly with many programming systems.
1.258 +
1.259 + Presently there are three contributed external interfaces included with
1.260 + the GLPK package:
1.261 +
1.262 + * GLPK Java Native Interface (JNI)
1.263 +
1.264 + * GLPK Delphi Interface (DELI)
1.265 +
1.266 + * GLPKMEX Matlab MEX interface
1.267 +
1.268 + There is an unofficial Microsoft Visual Basic, Tcl/Tk and Java GLPK
1.269 + interface available at
1.270 + <http://gottfried.lindner.bei.t-online.de/glpk.htm>.
1.271 +
1.272 + There are other language interfaces under development, including a Perl
1.273 + interface currently being developed by the FAQ maintainer, Dr. Harley
1.274 + Mackenzie <hjm@hardsoftware.com>.
1.275 +
1.276 +
1.277 + Q. Where can I find some examples?
1.278 +
1.279 + A. The GLPK package distribution contains many examples written in GNU
1.280 + MathProg (*.mod), C API calls (*.c), CPLEX input file format (*.lpt),
1.281 + MPS format (*.mps) as well as some specific Traveling Salesman examples
1.282 + (*.tsp).
1.283 +
1.284 + All of the examples can be found in the GLPK distribution examples
1.285 + sub-directory.
1.286 +
1.287 +
1.288 + Q. What are the future plans for GLPK?
1.289 +
1.290 + A. Developments planned for GLPK include improving the existing key
1.291 + GLPK components, such as developing a more robust and more efficient
1.292 + implementation of the simplex-based and interior-point solvers. Future
1.293 + GLPK enhancements planned are implementing a branch-and-cut solver, a
1.294 + MIP pre-processor, post-optimal and sensitivity analysis and possibly
1.295 + network simplex and quadratic programming solvers.
1.296 +
1.297 +
1.298 + Q. How do I report a GLPK bug?
1.299 +
1.300 + A. If you think you have found a bug in GLPK, then you should send as
1.301 + complete a report as possible to <bug-glpk@gnu.org>.
1.302 +
1.303 +
1.304 + Q. How do I contribute to the GLPK development?
1.305 +
1.306 + A. At present new GLPK development patches should be emailed to Andrew
1.307 + Makhorin <mao@mai2.rcnet.ru >, with sufficient documentation and test
1.308 + code to explain the nature of the patch, how to install it and the
1.309 + implications of its use. Before commencing any major GLPK development
1.310 + for inclusion in the GLPK distribution, it would be a good idea to
1.311 + discuss the idea on the GLPK mailing list.
1.312 +
1.313 +
1.314 + Q. How do I compile and link a GLPK application on a UNIX platform?
1.315 +
1.316 + A. To compile a GLPK application on a UNIX platform, then compiler must
1.317 + be able to include the GLPK include files and link to the GLPK library.
1.318 + For example, on a system where the GLPK system is installed:
1.319 +
1.320 + gcc mylp.c -o mylp -lglpk
1.321 +
1.322 + or specify the include files and libglpk.a explicitly, if GLPK is not
1.323 + installed.
1.324 +
1.325 +
1.326 + Q. How do I compile and link a GLPK application on a Win32 platform?
1.327 +
1.328 + A. On a Win32 platform, GLPK is implemented either as a Win32 Dynamic
1.329 + Link Library (DLL) or can be statically linked to the glpk*.lib file.
1.330 + As with the UNIX instructions, a GLPK application must set a path to
1.331 + the GLPK include files and also reference the GLPK library if
1.332 + statically linked.
1.333 +
1.334 +
1.335 + Q. How do I limit the GLPK execution time?
1.336 +
1.337 + A. You can limit the computing time by setting the control parameter
1.338 + LPX_K_TMLIM via the API routine lpx_set_real_parm . At present there is
1.339 + no way of limiting the execution time of glpsol without changing the
1.340 + source and recompiling a specific version.
1.341 +
1.342 +
1.343 +GLPK Linear Programming
1.344 +
1.345 + Q. What is Linear Programming and how does it work?
1.346 +
1.347 + A. Linear Programming is a mathematical technique that is a generic
1.348 + method for solving certain systems of equations with linear terms. The
1.349 + real power of LP's are that they have many practical applications and
1.350 + have proven to be a powerful and robust tool.
1.351 +
1.352 + The best single source of information on LP's is the Linear Programming
1.353 + FAQ
1.354 + <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html>
1.355 + that has information on LP's and MIP's, includes a comprehensive list
1.356 + of available LP software and has many LP references for further study.
1.357 +
1.358 +
1.359 + Q. How do I determine the stability of an LP solution?
1.360 +
1.361 + A. You can perform sensitivity analysis by specifying the --bounds
1.362 + option for glpsol as:
1.363 +
1.364 + glpsol ... --bounds filename
1.365 +
1.366 + in which case the solver writes results of the analysis to the
1.367 + specified filename in plain text format. The corresponding API routine
1.368 + is lpx_print_sens_bnds() .
1.369 +
1.370 +
1.371 + Q. How do I determine which constraints are causing infeasibility?
1.372 +
1.373 + A straightforward way to find such a set of constraints is to drop
1.374 + constraints one at a time. If dropping a constraint results in a
1.375 + solvable problem, pick it up and go on to the next constraint. After
1.376 + applying phase 1 to an infeasible problem, all basic satisfied
1.377 + constraints may be dropped.
1.378 +
1.379 + If the problem has a feasible dual, then running the dual simplex
1.380 + method is a more direct approach. After the last pivot, the nonbasic
1.381 + constraints and one of the violated constraints will constitute a
1.382 + minimal set. The GLPK simplex table routines will allow you to pick a
1.383 + correct constraint from the violated ones.
1.384 +
1.385 + Note that the GLPK pre-solver needs to be turned off for the preceding
1.386 + technique to work, otherwise GLPK does not keep the basis of an
1.387 + infeasible solution.
1.388 +
1.389 + Also a more detailed methodology has been posted on the mail list
1.390 + archive at
1.391 + <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>.
1.392 +
1.393 +
1.394 + Q. What is the difference between checks and constraints?
1.395 +
1.396 + A. Check statements are intended to check that all data specified by
1.397 + the user of the model are correct, mainly in the data section of a
1.398 + MathProg model. For example, if some parameter means the number of
1.399 + nodes in a network, it must be positive integer, that is just the
1.400 + condition to be checked in the check statement (although in this case
1.401 + such condition may be also checked directly in the parameter
1.402 + statement). Note that check statements are performed when the
1.403 + translator is generating the model, so they cannot include variables.
1.404 +
1.405 + Constraints are conditions that are expressed in terms of variables and
1.406 + resolved by the solver after the model has been completely generated.
1.407 + If all data specified in the model are correct a priori, check
1.408 + statements are not needed and can be omitted, while constraints are
1.409 + essential components of the model and therefore cannot be omitted.
1.410 +
1.411 +
1.412 +GLPK Integer Programming
1.413 +
1.414 + Q. What is Integer Programming and how does it work?
1.415 +
1.416 + A. Integer LP models are ones whose variables are constrained to take
1.417 + integer or whole number (as opposed to fractional) values. It may not
1.418 + be obvious that integer programming is a very much harder problem than
1.419 + ordinary linear programming, but that is nonetheless the case, in both
1.420 + theory and practice.
1.421 +
1.422 +
1.423 + Q. What is the Integer Optimization Suite (IOS)?
1.424 +
1.425 + A. IOS is a framework to implement implicit enumeration methods based
1.426 + on LP relaxation (like branch-and-bound and branch-and-cut). Currently
1.427 + IOS includes only basic features (the enumeration tree, API routines,
1.428 + and the driver) and is not completely documented.
1.429 +
1.430 +
1.431 + Q. I have just changed an LP to a MIP and now it doesn't work?
1.432 +
1.433 + A. If you have an existing LP that is working and you change to an MIP
1.434 + and receive a "lpx_integer: optimal solution of LP relaxation required"
1.435 + 204 (==LPX_E_FAULT) error, you probably have not called the LP solution
1.436 + method lpx_simplex() before lpx_integer() . The MIP routines use the LP
1.437 + solution as part of the MIP solution methodology.
1.438 +