lemon-project-template-glpk
view deps/glpk/doc/glpk_faq.txt @ 9:33de93886c88
Import GLPK 4.47
| author | Alpar Juttner <alpar@cs.elte.hu> |
|---|---|
| date | Sun, 06 Nov 2011 20:59:10 +0100 |
| parents | |
| children |
line source
2 GNU Linear Programming Kit FAQ
4 Summary: Frequently Asked Questions about the GNU Linear Programming Kit
6 Author: Dr. Harley Mackenzie <hjm@hardsoftware.com>
8 Posting-Frequency: Monthly
10 Language: English
12 $Date: 2004/01/09 05:57:57 $
14 $Revision: 1.6 $
18 Introduction
20 Q. What is GPLK?
22 A. GLPK stands for the GNU Linear Programming Kit. The GLPK package is
23 a set of routines written in ANSI C and organized in the form of a
24 callable library. This package is intended for solving large-scale
25 linear programming (LP), mixed integer linear programming (MIP), and
26 other related problems.
28 The GLPK package includes the following main components:
30 * implementation of the simplex method,
32 * implementation of the primal-dual interior point method,
34 * implementation of the branch-and-bound method,
36 * application program interface (API),
38 * GNU MathProg modeling language (a subset of AMPL),
40 * GLPSOL, a stand-alone LP/MIP solver.
43 Q. Who develops and maintains GLPK?
45 A. GLPK is currently developed and maintained by Andrew Makhorin,
46 Department for Applied Informatics, Moscow Aviation Institute, Moscow,
47 Russia. Andrew's email address is <mao@mai2.rcnet.ru> and his postal
48 address is 125871, Russia, Moscow, Volokolamskoye sh., 4, Moscow
49 Aviation Institute, Andrew O. Makhorin
52 Q. How is GLPK licensed?
54 A. GLPK is currently licensed under the GNU General Public License
55 (GPL). GLPK is free software; you can redistribute it and/or modify it
56 under the terms of the GNU General Public License as published by the
57 Free Software Foundation; either version 2, or (at your option) any
58 later version.
60 GLPK is not licensed under the Lesser General Public License (LGPL) as
61 distinct from other free LP codes such as lp_solve. The most
62 significant implication is that code that is linked to the GLPK library
63 must be released under the GPL, whereas with the LGPL, code linked to
64 the library does not have to be released under the same license.
67 Q. Where is the GLPK home page?
69 The GLPK home page is part of the GNU web site and can found at
70 <http://www.gnu.org/software/glpk/glpk.html>.
73 Q. How do I download and install GLPK?
75 A. The GLPK source distribution can be found in the subdirectory
76 /gnu/glpk/ on your favorite GNU mirror
77 <http://www.gnu.org/prep/ftp.html> and can be compiled directly from
78 the source.
80 The GLPK package (like all other GNU software) is distributed in the
81 form of packed archive. This is one file named 'glpk-x.y.tar.gz', where
82 x is the major version number and y is the minor version number.
84 In order to prepare the distribution for installation you should:
86 1. Copy the GLPK distribution file to some subdirectory.
88 2. Enter the command 'gzip -d glpk-x.y.tar.gz' in order to unpack the
89 distribution file. After unpacking the name of the distribution file
90 will be automatically changed to 'glpk-x.y.tar'.
92 3. Enter the command 'tar -x < glpk-x.y.tar' in order to unarchive the
93 distribution. After this operation the subdirectory 'glpk-x.y' which is
94 the GLPK distribution will have been automatically created.
96 After you have unpacked and unarchived GLPK distribution you should
97 configure the package, and compiled the application. The result of
98 compilation is:
100 * the file 'libglpk.a', which is a library archive containing object code
101 for all GLPK routines; and
103 * the program 'glpsol', which is a stand-alone LP/MIP solver.
105 Complete compilation and installation instructions are included in the
106 INSTALL file included with the distribution.
108 The distribution includes make files for the Microsoft Visual C/C++
109 version 6 and Borland C/C++ version 5 and by default compiles and links
110 a glpk*.lib library file, a glpk*.dll DLL file and an glpsol.exe
111 application file. A GNU Windows 4.1 binary, source and documentation
112 compiled using the mingw32 C/C++ compiler is also available from
113 <http://gnuwin32.sourceforge.net/packages/glpk.htm>.
116 Q. Is there a GLPK mailing list or newsgroup?
118 A. GLPK has two mailing lists: <help-glpk@gnu.org> and
119 <bug-glpk@gnu.org>.
121 The main discussion list is <help-glpk@gnu.org>, and is used to discuss
122 all aspects of GLPK, including its development and porting. There is
123 also a special list used for reporting bugs at <bug-glpk@gnu.org>.
125 To subscribe to any GLPK mailing list, send an empty mail with a
126 Subject: header line of just "subscribe" to the relevant -request list.
127 For example, to subscribe yourself to the main list, you would send
128 mail to <help-glpk-request@gnu.org> with no body and a Subject: header
129 line of just "subscribe".
131 Another way to subscribe to the GLP mailing lists is to visit the web
132 pages <http://mail.gnu.org/mailman/listinfo/help-glpk> and
133 <http://mail.gnu.org/mailman/listinfo/bug-glpk>.
135 Currently there are no newsgroups dedicated to GLPK.
138 Q. Who maintains this FAQ and how do I contribute to this FAQ?
140 A. The present maintainer of this FAQ is Dr. Harley Mackenzie, HARD
141 software, although the content of the FAQ is derived from many sources
142 such as GLPK documentation, GLPK email archives and original content.
144 Harley's email address is <hjm@hardsoftware.com> and his postal address
145 is c/o HARD software, PO Box 8004, Newtown, Victoria 3220, Australia.
147 All contributions to this FAQ, such as questions and (preferably)
148 answers should be sent to the <hjm@hardsoftware.com> email address.
149 This FAQ is copyright Harley Mackenzie 2003 and is released under the
150 same license, terms and conditions as GLPK, that is, GPL version 2 or
151 later.
153 Contributions are not directly referenced in the body of the FAQ as
154 this would become unmanageable and messy, but rather as a list of
155 contributors to this FAQ. If you are the author of any information
156 included in this FAQ and you do not want your content to be included,
157 please contact the FAQ maintainer and your material will be removed.
158 Also if you have not been correctly included as a contributor to this
159 FAQ, your details have changed, or you do not want your name listed in
160 the list of contributors, please contact the FAQ maintainer for
161 correction.
164 Q. Where can I download this FAQ?
166 The latest version of the GLPK FAQ is available to download from
167 <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> in the following
168 formats:
170 * DocBook
172 * Formatted text
174 * Adobe PDF
177 Q. Who are the FAQ contributors?
179 A. The FAQ contents were created from the following sources:
181 * Michael Hennebry
183 * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
185 * Harley Mackenzie, HARD software Pty. Ltd.
187 * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation
188 Institute
191 GLPK functions & features
193 Q. What is the current state of GLPK development?
195 A. GLPK is a work in progress and is presently under continual
196 development. As of the current version 4.3, GLPK is a simplex-based
197 solver is able to handle problems with up to 100,000 constraints. In
198 particular, it successfully solves all instances from netlib (see the
199 file bench.txt included in the GLPK distribution). The interior-point
200 solver is not very robust as it is unable to handle dense columns,
201 sometimes terminates due to numeric instability or slow convergence.
203 The Mixed Integer Programming (MIP) solver currently is based on
204 branch-and-bound, so it is unable to solve hard or very large problems
205 with a probable practical limit of 100-200 integer variables. However,
206 sometimes it is able to solve larger problems of up to 1000 integer
207 variables, although the size that depends on properties of particular
208 problem.
211 Q. How does GLPK compare with other LP codes?
213 A. I think that on very large-scale instances CPLEX 8.0 dual simplex is
214 10-100 times faster than the GLPK simplex solver and, of course, much
215 more robust. In many cases GLPK is faster and more robust than lp_solve
216 4.0 for pure LPs as well as MIP's. See the bench.txt file in the GLPK
217 distribution doc directory for GLPK netlib benchmark results.
219 You can find benchmarks for some LP and MIP solvers such as CPLEX,
220 GLPK, lp_solve, and OSL on Hans Mittelmann's webpage at
221 <http://plato.asu.edu/bench.html>.
224 Q. What are the differences between AMPL and GNU MathProg?
226 A. The subset of AMPL implemented in MathProg approximately corresponds
227 to AMPL status in 1990, because it is mainly based on the paper Robert
228 Fourer, David M Gay and Brian W Kernighan (1990), "A Modeling Language
229 for Mathematical Programming", Management Science, Vol 36, pp. 519-554
230 and is available at
231 <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf>.
233 The GNU MathProg translator was developed as part of GLPK. However, GNU
234 MathProg can be easily used in other applications as there is a set of
235 MathProg interface routines designed for use in other applications.
238 Q. What input file formats does GLPK support?
240 A. GLPK presently can read input and output LP model files in three
241 supported formats:
243 * MPS format - which is a column oriented and widely supported file
244 format but has poor human readability.
246 * CPLEX format - which is an easily readable row oriented format.
248 * GNU MathProg - which is an AMPL like mathematical modeling language.
251 Q. What interfaces are available for GLPK?
253 A. The GLPK package is in fact a C API that can be either by statically
254 or dynamically linked directly with many programming systems.
256 Presently there are three contributed external interfaces included with
257 the GLPK package:
259 * GLPK Java Native Interface (JNI)
261 * GLPK Delphi Interface (DELI)
263 * GLPKMEX Matlab MEX interface
265 There is an unofficial Microsoft Visual Basic, Tcl/Tk and Java GLPK
266 interface available at
267 <http://gottfried.lindner.bei.t-online.de/glpk.htm>.
269 There are other language interfaces under development, including a Perl
270 interface currently being developed by the FAQ maintainer, Dr. Harley
271 Mackenzie <hjm@hardsoftware.com>.
274 Q. Where can I find some examples?
276 A. The GLPK package distribution contains many examples written in GNU
277 MathProg (*.mod), C API calls (*.c), CPLEX input file format (*.lpt),
278 MPS format (*.mps) as well as some specific Traveling Salesman examples
279 (*.tsp).
281 All of the examples can be found in the GLPK distribution examples
282 sub-directory.
285 Q. What are the future plans for GLPK?
287 A. Developments planned for GLPK include improving the existing key
288 GLPK components, such as developing a more robust and more efficient
289 implementation of the simplex-based and interior-point solvers. Future
290 GLPK enhancements planned are implementing a branch-and-cut solver, a
291 MIP pre-processor, post-optimal and sensitivity analysis and possibly
292 network simplex and quadratic programming solvers.
295 Q. How do I report a GLPK bug?
297 A. If you think you have found a bug in GLPK, then you should send as
298 complete a report as possible to <bug-glpk@gnu.org>.
301 Q. How do I contribute to the GLPK development?
303 A. At present new GLPK development patches should be emailed to Andrew
304 Makhorin <mao@mai2.rcnet.ru >, with sufficient documentation and test
305 code to explain the nature of the patch, how to install it and the
306 implications of its use. Before commencing any major GLPK development
307 for inclusion in the GLPK distribution, it would be a good idea to
308 discuss the idea on the GLPK mailing list.
311 Q. How do I compile and link a GLPK application on a UNIX platform?
313 A. To compile a GLPK application on a UNIX platform, then compiler must
314 be able to include the GLPK include files and link to the GLPK library.
315 For example, on a system where the GLPK system is installed:
317 gcc mylp.c -o mylp -lglpk
319 or specify the include files and libglpk.a explicitly, if GLPK is not
320 installed.
323 Q. How do I compile and link a GLPK application on a Win32 platform?
325 A. On a Win32 platform, GLPK is implemented either as a Win32 Dynamic
326 Link Library (DLL) or can be statically linked to the glpk*.lib file.
327 As with the UNIX instructions, a GLPK application must set a path to
328 the GLPK include files and also reference the GLPK library if
329 statically linked.
332 Q. How do I limit the GLPK execution time?
334 A. You can limit the computing time by setting the control parameter
335 LPX_K_TMLIM via the API routine lpx_set_real_parm . At present there is
336 no way of limiting the execution time of glpsol without changing the
337 source and recompiling a specific version.
340 GLPK Linear Programming
342 Q. What is Linear Programming and how does it work?
344 A. Linear Programming is a mathematical technique that is a generic
345 method for solving certain systems of equations with linear terms. The
346 real power of LP's are that they have many practical applications and
347 have proven to be a powerful and robust tool.
349 The best single source of information on LP's is the Linear Programming
350 FAQ
351 <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html>
352 that has information on LP's and MIP's, includes a comprehensive list
353 of available LP software and has many LP references for further study.
356 Q. How do I determine the stability of an LP solution?
358 A. You can perform sensitivity analysis by specifying the --bounds
359 option for glpsol as:
361 glpsol ... --bounds filename
363 in which case the solver writes results of the analysis to the
364 specified filename in plain text format. The corresponding API routine
365 is lpx_print_sens_bnds() .
368 Q. How do I determine which constraints are causing infeasibility?
370 A straightforward way to find such a set of constraints is to drop
371 constraints one at a time. If dropping a constraint results in a
372 solvable problem, pick it up and go on to the next constraint. After
373 applying phase 1 to an infeasible problem, all basic satisfied
374 constraints may be dropped.
376 If the problem has a feasible dual, then running the dual simplex
377 method is a more direct approach. After the last pivot, the nonbasic
378 constraints and one of the violated constraints will constitute a
379 minimal set. The GLPK simplex table routines will allow you to pick a
380 correct constraint from the violated ones.
382 Note that the GLPK pre-solver needs to be turned off for the preceding
383 technique to work, otherwise GLPK does not keep the basis of an
384 infeasible solution.
386 Also a more detailed methodology has been posted on the mail list
387 archive at
388 <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>.
391 Q. What is the difference between checks and constraints?
393 A. Check statements are intended to check that all data specified by
394 the user of the model are correct, mainly in the data section of a
395 MathProg model. For example, if some parameter means the number of
396 nodes in a network, it must be positive integer, that is just the
397 condition to be checked in the check statement (although in this case
398 such condition may be also checked directly in the parameter
399 statement). Note that check statements are performed when the
400 translator is generating the model, so they cannot include variables.
402 Constraints are conditions that are expressed in terms of variables and
403 resolved by the solver after the model has been completely generated.
404 If all data specified in the model are correct a priori, check
405 statements are not needed and can be omitted, while constraints are
406 essential components of the model and therefore cannot be omitted.
409 GLPK Integer Programming
411 Q. What is Integer Programming and how does it work?
413 A. Integer LP models are ones whose variables are constrained to take
414 integer or whole number (as opposed to fractional) values. It may not
415 be obvious that integer programming is a very much harder problem than
416 ordinary linear programming, but that is nonetheless the case, in both
417 theory and practice.
420 Q. What is the Integer Optimization Suite (IOS)?
422 A. IOS is a framework to implement implicit enumeration methods based
423 on LP relaxation (like branch-and-bound and branch-and-cut). Currently
424 IOS includes only basic features (the enumeration tree, API routines,
425 and the driver) and is not completely documented.
428 Q. I have just changed an LP to a MIP and now it doesn't work?
430 A. If you have an existing LP that is working and you change to an MIP
431 and receive a "lpx_integer: optimal solution of LP relaxation required"
432 204 (==LPX_E_FAULT) error, you probably have not called the LP solution
433 method lpx_simplex() before lpx_integer() . The MIP routines use the LP
434 solution as part of the MIP solution methodology.