lemon-project-template-glpk

annotate deps/glpk/doc/glpk_faq.txt @ 9:33de93886c88

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