[1] | 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 | |
---|