|
1 |
|
2 GNU Linear Programming Kit FAQ |
|
3 |
|
4 Summary: Frequently Asked Questions about the GNU Linear Programming Kit |
|
5 |
|
6 Author: Dr. Harley Mackenzie <hjm@hardsoftware.com> |
|
7 |
|
8 Posting-Frequency: Monthly |
|
9 |
|
10 Language: English |
|
11 |
|
12 $Date: 2004/01/09 05:57:57 $ |
|
13 |
|
14 $Revision: 1.6 $ |
|
15 |
|
16 |
|
17 |
|
18 Introduction |
|
19 |
|
20 Q. What is GPLK? |
|
21 |
|
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. |
|
27 |
|
28 The GLPK package includes the following main components: |
|
29 |
|
30 * implementation of the simplex method, |
|
31 |
|
32 * implementation of the primal-dual interior point method, |
|
33 |
|
34 * implementation of the branch-and-bound method, |
|
35 |
|
36 * application program interface (API), |
|
37 |
|
38 * GNU MathProg modeling language (a subset of AMPL), |
|
39 |
|
40 * GLPSOL, a stand-alone LP/MIP solver. |
|
41 |
|
42 |
|
43 Q. Who develops and maintains GLPK? |
|
44 |
|
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 |
|
50 |
|
51 |
|
52 Q. How is GLPK licensed? |
|
53 |
|
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. |
|
59 |
|
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. |
|
65 |
|
66 |
|
67 Q. Where is the GLPK home page? |
|
68 |
|
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>. |
|
71 |
|
72 |
|
73 Q. How do I download and install GLPK? |
|
74 |
|
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. |
|
79 |
|
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. |
|
83 |
|
84 In order to prepare the distribution for installation you should: |
|
85 |
|
86 1. Copy the GLPK distribution file to some subdirectory. |
|
87 |
|
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'. |
|
91 |
|
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. |
|
95 |
|
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: |
|
99 |
|
100 * the file 'libglpk.a', which is a library archive containing object code |
|
101 for all GLPK routines; and |
|
102 |
|
103 * the program 'glpsol', which is a stand-alone LP/MIP solver. |
|
104 |
|
105 Complete compilation and installation instructions are included in the |
|
106 INSTALL file included with the distribution. |
|
107 |
|
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>. |
|
114 |
|
115 |
|
116 Q. Is there a GLPK mailing list or newsgroup? |
|
117 |
|
118 A. GLPK has two mailing lists: <help-glpk@gnu.org> and |
|
119 <bug-glpk@gnu.org>. |
|
120 |
|
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>. |
|
124 |
|
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". |
|
130 |
|
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>. |
|
134 |
|
135 Currently there are no newsgroups dedicated to GLPK. |
|
136 |
|
137 |
|
138 Q. Who maintains this FAQ and how do I contribute to this FAQ? |
|
139 |
|
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. |
|
143 |
|
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. |
|
146 |
|
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. |
|
152 |
|
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. |
|
162 |
|
163 |
|
164 Q. Where can I download this FAQ? |
|
165 |
|
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: |
|
169 |
|
170 * DocBook |
|
171 |
|
172 * Formatted text |
|
173 |
|
174 * Adobe PDF |
|
175 |
|
176 |
|
177 Q. Who are the FAQ contributors? |
|
178 |
|
179 A. The FAQ contents were created from the following sources: |
|
180 |
|
181 * Michael Hennebry |
|
182 |
|
183 * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html |
|
184 |
|
185 * Harley Mackenzie, HARD software Pty. Ltd. |
|
186 |
|
187 * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation |
|
188 Institute |
|
189 |
|
190 |
|
191 GLPK functions & features |
|
192 |
|
193 Q. What is the current state of GLPK development? |
|
194 |
|
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. |
|
202 |
|
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. |
|
209 |
|
210 |
|
211 Q. How does GLPK compare with other LP codes? |
|
212 |
|
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. |
|
218 |
|
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>. |
|
222 |
|
223 |
|
224 Q. What are the differences between AMPL and GNU MathProg? |
|
225 |
|
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>. |
|
232 |
|
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. |
|
236 |
|
237 |
|
238 Q. What input file formats does GLPK support? |
|
239 |
|
240 A. GLPK presently can read input and output LP model files in three |
|
241 supported formats: |
|
242 |
|
243 * MPS format - which is a column oriented and widely supported file |
|
244 format but has poor human readability. |
|
245 |
|
246 * CPLEX format - which is an easily readable row oriented format. |
|
247 |
|
248 * GNU MathProg - which is an AMPL like mathematical modeling language. |
|
249 |
|
250 |
|
251 Q. What interfaces are available for GLPK? |
|
252 |
|
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. |
|
255 |
|
256 Presently there are three contributed external interfaces included with |
|
257 the GLPK package: |
|
258 |
|
259 * GLPK Java Native Interface (JNI) |
|
260 |
|
261 * GLPK Delphi Interface (DELI) |
|
262 |
|
263 * GLPKMEX Matlab MEX interface |
|
264 |
|
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>. |
|
268 |
|
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>. |
|
272 |
|
273 |
|
274 Q. Where can I find some examples? |
|
275 |
|
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). |
|
280 |
|
281 All of the examples can be found in the GLPK distribution examples |
|
282 sub-directory. |
|
283 |
|
284 |
|
285 Q. What are the future plans for GLPK? |
|
286 |
|
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. |
|
293 |
|
294 |
|
295 Q. How do I report a GLPK bug? |
|
296 |
|
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>. |
|
299 |
|
300 |
|
301 Q. How do I contribute to the GLPK development? |
|
302 |
|
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. |
|
309 |
|
310 |
|
311 Q. How do I compile and link a GLPK application on a UNIX platform? |
|
312 |
|
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: |
|
316 |
|
317 gcc mylp.c -o mylp -lglpk |
|
318 |
|
319 or specify the include files and libglpk.a explicitly, if GLPK is not |
|
320 installed. |
|
321 |
|
322 |
|
323 Q. How do I compile and link a GLPK application on a Win32 platform? |
|
324 |
|
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. |
|
330 |
|
331 |
|
332 Q. How do I limit the GLPK execution time? |
|
333 |
|
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. |
|
338 |
|
339 |
|
340 GLPK Linear Programming |
|
341 |
|
342 Q. What is Linear Programming and how does it work? |
|
343 |
|
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. |
|
348 |
|
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. |
|
354 |
|
355 |
|
356 Q. How do I determine the stability of an LP solution? |
|
357 |
|
358 A. You can perform sensitivity analysis by specifying the --bounds |
|
359 option for glpsol as: |
|
360 |
|
361 glpsol ... --bounds filename |
|
362 |
|
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() . |
|
366 |
|
367 |
|
368 Q. How do I determine which constraints are causing infeasibility? |
|
369 |
|
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. |
|
375 |
|
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. |
|
381 |
|
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. |
|
385 |
|
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>. |
|
389 |
|
390 |
|
391 Q. What is the difference between checks and constraints? |
|
392 |
|
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. |
|
401 |
|
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. |
|
407 |
|
408 |
|
409 GLPK Integer Programming |
|
410 |
|
411 Q. What is Integer Programming and how does it work? |
|
412 |
|
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. |
|
418 |
|
419 |
|
420 Q. What is the Integer Optimization Suite (IOS)? |
|
421 |
|
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. |
|
426 |
|
427 |
|
428 Q. I have just changed an LP to a MIP and now it doesn't work? |
|
429 |
|
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. |
|
435 |