COIN-OR::LEMON - Graph Library

source: lemon-project-template-glpk/deps/glpk/doc/glpk_faq.txt

subpack-glpk
Last change on this file was 9:33de93886c88, checked in by Alpar Juttner <alpar@…>, 13 years ago

Import GLPK 4.47

File size: 20.8 KB
Line 
1
2GNU 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
18Introduction
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
191GLPK 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
340GLPK 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
409GLPK 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
Note: See TracBrowser for help on using the repository browser.