1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/deps/glpk/doc/glpk_faq.txt	Sun Nov 06 20:59:10 2011 +0100
     1.3 @@ -0,0 +1,435 @@
     1.4 +
     1.5 +GNU Linear Programming Kit FAQ
     1.6 +
     1.7 +  Summary: Frequently Asked Questions about the GNU Linear Programming Kit
     1.8 +
     1.9 +  Author: Dr. Harley Mackenzie <hjm@hardsoftware.com>                     
    1.10 +
    1.11 +  Posting-Frequency: Monthly                                              
    1.12 +
    1.13 +  Language: English                                                       
    1.14 +
    1.15 +  $Date: 2004/01/09 05:57:57 $                                            
    1.16 +
    1.17 +  $Revision: 1.6 $                                                        
    1.18 +
    1.19 +
    1.20 +
    1.21 +Introduction
    1.22 +
    1.23 +  Q. What is GPLK?                                                        
    1.24 +
    1.25 +  A. GLPK stands for the GNU Linear Programming Kit. The GLPK package is  
    1.26 +  a set of routines written in ANSI C and organized in the form of a      
    1.27 +  callable library. This package is intended for solving large-scale      
    1.28 +  linear programming (LP), mixed integer linear programming (MIP), and    
    1.29 +  other related problems.                                                 
    1.30 +
    1.31 +  The GLPK package includes the following main components:                
    1.32 +
    1.33 +    * implementation of the simplex method,                                   
    1.34 +
    1.35 +    * implementation of the primal-dual interior point method,                
    1.36 +
    1.37 +    * implementation of the branch-and-bound method,                          
    1.38 +
    1.39 +    * application program interface (API),                                    
    1.40 +
    1.41 +    * GNU MathProg modeling language (a subset of AMPL),                      
    1.42 +
    1.43 +    * GLPSOL, a stand-alone LP/MIP solver.                                    
    1.44 +
    1.45 +
    1.46 +  Q. Who develops and maintains GLPK?                                     
    1.47 +
    1.48 +  A. GLPK is currently developed and maintained by Andrew Makhorin,       
    1.49 +  Department for Applied Informatics, Moscow Aviation Institute, Moscow,  
    1.50 +  Russia. Andrew's email address is <mao@mai2.rcnet.ru> and his postal    
    1.51 +  address is 125871, Russia, Moscow, Volokolamskoye sh., 4, Moscow        
    1.52 +  Aviation Institute, Andrew O. Makhorin                                  
    1.53 +
    1.54 +
    1.55 +  Q. How is GLPK licensed?                                                
    1.56 +
    1.57 +  A. GLPK is currently licensed under the GNU General Public License      
    1.58 +  (GPL). GLPK is free software; you can redistribute it and/or modify it  
    1.59 +  under the terms of the GNU General Public License as published by the   
    1.60 +  Free Software Foundation; either version 2, or (at your option) any     
    1.61 +  later version.                                                          
    1.62 +
    1.63 +  GLPK is not licensed under the Lesser General Public License (LGPL) as  
    1.64 +  distinct from other free LP codes such as lp_solve. The most            
    1.65 +  significant implication is that code that is linked to the GLPK library 
    1.66 +  must be released under the GPL, whereas with the LGPL, code linked to   
    1.67 +  the library does not have to be released under the same license.        
    1.68 +
    1.69 +
    1.70 +  Q. Where is the GLPK home page?                                         
    1.71 +
    1.72 +  The GLPK home page is part of the GNU web site and can found at         
    1.73 +  <http://www.gnu.org/software/glpk/glpk.html>.                           
    1.74 +
    1.75 +
    1.76 +  Q. How do I download and install GLPK?                                  
    1.77 +
    1.78 +  A. The GLPK source distribution can be found in the subdirectory        
    1.79 +  /gnu/glpk/ on your favorite GNU mirror                                  
    1.80 +  <http://www.gnu.org/prep/ftp.html> and can be compiled directly from    
    1.81 +  the source.                                                             
    1.82 +
    1.83 +  The GLPK package (like all other GNU software) is distributed in the    
    1.84 +  form of packed archive. This is one file named 'glpk-x.y.tar.gz', where 
    1.85 +  x is the major version number and y is the minor version number.        
    1.86 +
    1.87 +  In order to prepare the distribution for installation you should:       
    1.88 +
    1.89 +    1. Copy the GLPK distribution file to some subdirectory.                   
    1.90 +
    1.91 +    2. Enter the command 'gzip -d glpk-x.y.tar.gz' in order to unpack the      
    1.92 +       distribution file. After unpacking the name of the distribution file    
    1.93 +       will be automatically changed to 'glpk-x.y.tar'.                        
    1.94 +
    1.95 +    3. Enter the command 'tar -x < glpk-x.y.tar' in order to unarchive the     
    1.96 +       distribution. After this operation the subdirectory 'glpk-x.y' which is 
    1.97 +       the GLPK distribution will have been automatically created.             
    1.98 +
    1.99 +  After you have unpacked and unarchived GLPK distribution you should     
   1.100 +  configure the package, and compiled the application. The result of      
   1.101 +  compilation is:                                                         
   1.102 +
   1.103 +    * the file 'libglpk.a', which is a library archive containing object code 
   1.104 +      for all GLPK routines; and                                              
   1.105 +
   1.106 +    * the program 'glpsol', which is a stand-alone LP/MIP solver.             
   1.107 +
   1.108 +  Complete compilation and installation instructions are included in the  
   1.109 +  INSTALL file included with the distribution.                            
   1.110 +
   1.111 +  The distribution includes make files for the Microsoft Visual C/C++     
   1.112 +  version 6 and Borland C/C++ version 5 and by default compiles and links 
   1.113 +  a glpk*.lib library file, a glpk*.dll DLL file and an glpsol.exe        
   1.114 +  application file. A GNU Windows 4.1 binary, source and documentation    
   1.115 +  compiled using the mingw32 C/C++ compiler is also available from        
   1.116 +  <http://gnuwin32.sourceforge.net/packages/glpk.htm>.                    
   1.117 +
   1.118 +
   1.119 +  Q. Is there a GLPK mailing list or newsgroup?                           
   1.120 +
   1.121 +  A. GLPK has two mailing lists: <help-glpk@gnu.org> and                  
   1.122 +  <bug-glpk@gnu.org>.                                                     
   1.123 +
   1.124 +  The main discussion list is <help-glpk@gnu.org>, and is used to discuss 
   1.125 +  all aspects of GLPK, including its development and porting. There is    
   1.126 +  also a special list used for reporting bugs at <bug-glpk@gnu.org>.      
   1.127 +
   1.128 +  To subscribe to any GLPK mailing list, send an empty mail with a        
   1.129 +  Subject: header line of just "subscribe" to the relevant -request list. 
   1.130 +  For example, to subscribe yourself to the main list, you would send     
   1.131 +  mail to <help-glpk-request@gnu.org> with no body and a Subject: header  
   1.132 +  line of just "subscribe".                                               
   1.133 +
   1.134 +  Another way to subscribe to the GLP mailing lists is to visit the web   
   1.135 +  pages <http://mail.gnu.org/mailman/listinfo/help-glpk> and              
   1.136 +  <http://mail.gnu.org/mailman/listinfo/bug-glpk>.                        
   1.137 +
   1.138 +  Currently there are no newsgroups dedicated to GLPK.                    
   1.139 +
   1.140 +
   1.141 +  Q. Who maintains this FAQ and how do I contribute to this FAQ?          
   1.142 +
   1.143 +  A. The present maintainer of this FAQ is Dr. Harley Mackenzie, HARD     
   1.144 +  software, although the content of the FAQ is derived from many sources  
   1.145 +  such as GLPK documentation, GLPK email archives and original content.   
   1.146 +
   1.147 +  Harley's email address is <hjm@hardsoftware.com> and his postal address 
   1.148 +  is c/o HARD software, PO Box 8004, Newtown, Victoria 3220, Australia.   
   1.149 +
   1.150 +  All contributions to this FAQ, such as questions and (preferably)       
   1.151 +  answers should be sent to the <hjm@hardsoftware.com> email address.     
   1.152 +  This FAQ is copyright Harley Mackenzie 2003 and is released under the   
   1.153 +  same license, terms and conditions as GLPK, that is, GPL version 2 or   
   1.154 +  later.                                                                  
   1.155 +
   1.156 +  Contributions are not directly referenced in the body of the FAQ as     
   1.157 +  this would become unmanageable and messy, but rather as a list of       
   1.158 +  contributors to this FAQ. If you are the author of any information      
   1.159 +  included in this FAQ and you do not want your content to be included,   
   1.160 +  please contact the FAQ maintainer and your material will be removed.    
   1.161 +  Also if you have not been correctly included as a contributor to this   
   1.162 +  FAQ, your details have changed, or you do not want your name listed in  
   1.163 +  the list of contributors, please contact the FAQ maintainer for         
   1.164 +  correction.                                                             
   1.165 +
   1.166 +
   1.167 +  Q. Where can I download this FAQ?                                       
   1.168 +
   1.169 +  The latest version of the GLPK FAQ is available to download from        
   1.170 +  <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> in the following   
   1.171 +  formats:                                                                
   1.172 +
   1.173 +    * DocBook                                                                 
   1.174 +
   1.175 +    * Formatted text                                                          
   1.176 +
   1.177 +    * Adobe PDF                                                               
   1.178 +
   1.179 +
   1.180 +  Q. Who are the FAQ contributors?                                        
   1.181 +
   1.182 +  A. The FAQ contents were created from the following sources:            
   1.183 +
   1.184 +    * Michael Hennebry                                                        
   1.185 +
   1.186 +    * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html   
   1.187 +
   1.188 +    * Harley Mackenzie, HARD software Pty. Ltd.                               
   1.189 +
   1.190 +    * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation    
   1.191 +      Institute                                                               
   1.192 +
   1.193 +
   1.194 +GLPK functions & features
   1.195 +
   1.196 +  Q. What is the current state of GLPK development?                       
   1.197 +
   1.198 +  A. GLPK is a work in progress and is presently under continual          
   1.199 +  development. As of the current version 4.3, GLPK is a simplex-based     
   1.200 +  solver is able to handle problems with up to 100,000 constraints. In    
   1.201 +  particular, it successfully solves all instances from netlib (see the   
   1.202 +  file bench.txt included in the GLPK distribution). The interior-point   
   1.203 +  solver is not very robust as it is unable to handle dense columns,      
   1.204 +  sometimes terminates due to numeric instability or slow convergence.    
   1.205 +
   1.206 +  The Mixed Integer Programming (MIP) solver currently is based on        
   1.207 +  branch-and-bound, so it is unable to solve hard or very large problems  
   1.208 +  with a probable practical limit of 100-200 integer variables. However,  
   1.209 +  sometimes it is able to solve larger problems of up to 1000 integer     
   1.210 +  variables, although the size that depends on properties of particular   
   1.211 +  problem.                                                                
   1.212 +
   1.213 +
   1.214 +  Q. How does GLPK compare with other LP codes?                           
   1.215 +
   1.216 +  A. I think that on very large-scale instances CPLEX 8.0 dual simplex is 
   1.217 +  10-100 times faster than the GLPK simplex solver and, of course, much   
   1.218 +  more robust. In many cases GLPK is faster and more robust than lp_solve 
   1.219 +  4.0 for pure LPs as well as MIP's. See the bench.txt file in the GLPK   
   1.220 +  distribution doc directory for GLPK netlib benchmark results.           
   1.221 +
   1.222 +  You can find benchmarks for some LP and MIP solvers such as CPLEX,      
   1.223 +  GLPK, lp_solve, and OSL on Hans Mittelmann's webpage at                 
   1.224 +  <http://plato.asu.edu/bench.html>.                                      
   1.225 +
   1.226 +
   1.227 +  Q. What are the differences between AMPL and GNU MathProg?              
   1.228 +
   1.229 +  A. The subset of AMPL implemented in MathProg approximately corresponds 
   1.230 +  to AMPL status in 1990, because it is mainly based on the paper Robert  
   1.231 +  Fourer, David M Gay and Brian W Kernighan (1990), "A Modeling Language  
   1.232 +  for Mathematical Programming", Management Science, Vol 36, pp. 519-554  
   1.233 +  and is available at                                                     
   1.234 +  <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf>.                  
   1.235 +
   1.236 +  The GNU MathProg translator was developed as part of GLPK. However, GNU 
   1.237 +  MathProg can be easily used in other applications as there is a set of  
   1.238 +  MathProg interface routines designed for use in other applications.     
   1.239 +
   1.240 +
   1.241 +  Q. What input file formats does GLPK support?                           
   1.242 +
   1.243 +  A. GLPK presently can read input and output LP model files in three     
   1.244 +  supported formats:                                                      
   1.245 +
   1.246 +    * MPS format - which is a column oriented and widely supported file       
   1.247 +      format but has poor human readability.                                  
   1.248 +
   1.249 +    * CPLEX format - which is an easily readable row oriented format.         
   1.250 +
   1.251 +    * GNU MathProg - which is an AMPL like mathematical modeling language.    
   1.252 +
   1.253 +
   1.254 +  Q. What interfaces are available for GLPK?                              
   1.255 +
   1.256 +  A. The GLPK package is in fact a C API that can be either by statically 
   1.257 +  or dynamically linked directly with many programming systems.           
   1.258 +
   1.259 +  Presently there are three contributed external interfaces included with 
   1.260 +  the GLPK package:                                                       
   1.261 +
   1.262 +    * GLPK Java Native Interface (JNI)                                        
   1.263 +
   1.264 +    * GLPK Delphi Interface (DELI)                                            
   1.265 +
   1.266 +    * GLPKMEX Matlab MEX interface                                            
   1.267 +
   1.268 +  There is an unofficial Microsoft Visual Basic, Tcl/Tk and Java GLPK     
   1.269 +  interface available at                                                  
   1.270 +  <http://gottfried.lindner.bei.t-online.de/glpk.htm>.                    
   1.271 +
   1.272 +  There are other language interfaces under development, including a Perl 
   1.273 +  interface currently being developed by the FAQ maintainer, Dr. Harley   
   1.274 +  Mackenzie <hjm@hardsoftware.com>.                                       
   1.275 +
   1.276 +
   1.277 +  Q. Where can I find some examples?                                      
   1.278 +
   1.279 +  A. The GLPK package distribution contains many examples written in GNU  
   1.280 +  MathProg (*.mod), C API calls (*.c), CPLEX input file format (*.lpt),   
   1.281 +  MPS format (*.mps) as well as some specific Traveling Salesman examples 
   1.282 +  (*.tsp).                                                                
   1.283 +
   1.284 +  All of the examples can be found in the GLPK distribution examples      
   1.285 +  sub-directory.                                                          
   1.286 +
   1.287 +
   1.288 +  Q. What are the future plans for GLPK?                                  
   1.289 +
   1.290 +  A. Developments planned for GLPK include improving the existing key     
   1.291 +  GLPK components, such as developing a more robust and more efficient    
   1.292 +  implementation of the simplex-based and interior-point solvers. Future  
   1.293 +  GLPK enhancements planned are implementing a branch-and-cut solver, a   
   1.294 +  MIP pre-processor, post-optimal and sensitivity analysis and possibly   
   1.295 +  network simplex and quadratic programming solvers.                      
   1.296 +
   1.297 +
   1.298 +  Q. How do I report a GLPK bug?                                          
   1.299 +
   1.300 +  A. If you think you have found a bug in GLPK, then you should send as   
   1.301 +  complete a report as possible to <bug-glpk@gnu.org>.                    
   1.302 +
   1.303 +
   1.304 +  Q. How do I contribute to the GLPK development?                         
   1.305 +
   1.306 +  A. At present new GLPK development patches should be emailed to Andrew  
   1.307 +  Makhorin <mao@mai2.rcnet.ru >, with sufficient documentation and test   
   1.308 +  code to explain the nature of the patch, how to install it and the      
   1.309 +  implications of its use. Before commencing any major GLPK development   
   1.310 +  for inclusion in the GLPK distribution, it would be a good idea to      
   1.311 +  discuss the idea on the GLPK mailing list.                              
   1.312 +
   1.313 +
   1.314 +  Q. How do I compile and link a GLPK application on a UNIX platform?     
   1.315 +
   1.316 +  A. To compile a GLPK application on a UNIX platform, then compiler must 
   1.317 +  be able to include the GLPK include files and link to the GLPK library. 
   1.318 +  For example, on a system where the GLPK system is installed:            
   1.319 +
   1.320 +  gcc mylp.c -o mylp -lglpk                                               
   1.321 +
   1.322 +  or specify the include files and libglpk.a explicitly, if GLPK is not   
   1.323 +  installed.                                                              
   1.324 +
   1.325 +
   1.326 +  Q. How do I compile and link a GLPK application on a Win32 platform?    
   1.327 +
   1.328 +  A. On a Win32 platform, GLPK is implemented either as a Win32 Dynamic   
   1.329 +  Link Library (DLL) or can be statically linked to the glpk*.lib file.   
   1.330 +  As with the UNIX instructions, a GLPK application must set a path to    
   1.331 +  the GLPK include files and also reference the GLPK library if           
   1.332 +  statically linked.                                                      
   1.333 +
   1.334 +
   1.335 +  Q. How do I limit the GLPK execution time?                              
   1.336 +
   1.337 +  A. You can limit the computing time by setting the control parameter    
   1.338 +  LPX_K_TMLIM via the API routine lpx_set_real_parm . At present there is 
   1.339 +  no way of limiting the execution time of glpsol without changing the    
   1.340 +  source and recompiling a specific version.                              
   1.341 +
   1.342 +
   1.343 +GLPK Linear Programming
   1.344 +
   1.345 +  Q. What is Linear Programming and how does it work?                     
   1.346 +
   1.347 +  A. Linear Programming is a mathematical technique that is a generic     
   1.348 +  method for solving certain systems of equations with linear terms. The  
   1.349 +  real power of LP's are that they have many practical applications and   
   1.350 +  have proven to be a powerful and robust tool.                           
   1.351 +
   1.352 +  The best single source of information on LP's is the Linear Programming 
   1.353 +  FAQ                                                                     
   1.354 +  <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html> 
   1.355 +  that has information on LP's and MIP's, includes a comprehensive list   
   1.356 +  of available LP software and has many LP references for further study.  
   1.357 +
   1.358 +
   1.359 +  Q. How do I determine the stability of an LP solution?                  
   1.360 +
   1.361 +  A. You can perform sensitivity analysis by specifying the --bounds      
   1.362 +  option for glpsol as:                                                   
   1.363 +
   1.364 +  glpsol ... --bounds filename                                            
   1.365 +
   1.366 +  in which case the solver writes results of the analysis to the          
   1.367 +  specified filename in plain text format. The corresponding API routine  
   1.368 +  is lpx_print_sens_bnds() .                                              
   1.369 +
   1.370 +
   1.371 +  Q. How do I determine which constraints are causing infeasibility?      
   1.372 +
   1.373 +  A straightforward way to find such a set of constraints is to drop      
   1.374 +  constraints one at a time. If dropping a constraint results in a        
   1.375 +  solvable problem, pick it up and go on to the next constraint. After    
   1.376 +  applying phase 1 to an infeasible problem, all basic satisfied          
   1.377 +  constraints may be dropped.                                             
   1.378 +
   1.379 +  If the problem has a feasible dual, then running the dual simplex       
   1.380 +  method is a more direct approach. After the last pivot, the nonbasic    
   1.381 +  constraints and one of the violated constraints will constitute a       
   1.382 +  minimal set. The GLPK simplex table routines will allow you to pick a   
   1.383 +  correct constraint from the violated ones.                              
   1.384 +
   1.385 +  Note that the GLPK pre-solver needs to be turned off for the preceding  
   1.386 +  technique to work, otherwise GLPK does not keep the basis of an         
   1.387 +  infeasible solution.                                                    
   1.388 +
   1.389 +  Also a more detailed methodology has been posted on the mail list       
   1.390 +  archive at                                                              
   1.391 +  <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>.     
   1.392 +
   1.393 +
   1.394 +  Q. What is the difference between checks and constraints?               
   1.395 +
   1.396 +  A. Check statements are intended to check that all data specified by    
   1.397 +  the user of the model are correct, mainly in the data section of a      
   1.398 +  MathProg model. For example, if some parameter means the number of      
   1.399 +  nodes in a network, it must be positive integer, that is just the       
   1.400 +  condition to be checked in the check statement (although in this case   
   1.401 +  such condition may be also checked directly in the parameter            
   1.402 +  statement). Note that check statements are performed when the           
   1.403 +  translator is generating the model, so they cannot include variables.   
   1.404 +
   1.405 +  Constraints are conditions that are expressed in terms of variables and 
   1.406 +  resolved by the solver after the model has been completely generated.   
   1.407 +  If all data specified in the model are correct a priori, check          
   1.408 +  statements are not needed and can be omitted, while constraints are     
   1.409 +  essential components of the model and therefore cannot be omitted.      
   1.410 +
   1.411 +
   1.412 +GLPK Integer Programming 
   1.413 +
   1.414 +  Q. What is Integer Programming and how does it work?                    
   1.415 +
   1.416 +  A. Integer LP models are ones whose variables are constrained to take   
   1.417 +  integer or whole number (as opposed to fractional) values. It may not   
   1.418 +  be obvious that integer programming is a very much harder problem than  
   1.419 +  ordinary linear programming, but that is nonetheless the case, in both  
   1.420 +  theory and practice.                                                    
   1.421 +
   1.422 +
   1.423 +  Q. What is the Integer Optimization Suite (IOS)?                        
   1.424 +
   1.425 +  A. IOS is a framework to implement implicit enumeration methods based   
   1.426 +  on LP relaxation (like branch-and-bound and branch-and-cut). Currently  
   1.427 +  IOS includes only basic features (the enumeration tree, API routines,   
   1.428 +  and the driver) and is not completely documented.                       
   1.429 +
   1.430 +
   1.431 +  Q. I have just changed an LP to a MIP and now it doesn't work?          
   1.432 +
   1.433 +  A. If you have an existing LP that is working and you change to an MIP  
   1.434 +  and receive a "lpx_integer: optimal solution of LP relaxation required" 
   1.435 +  204 (==LPX_E_FAULT) error, you probably have not called the LP solution 
   1.436 +  method lpx_simplex() before lpx_integer() . The MIP routines use the LP 
   1.437 +  solution as part of the MIP solution methodology.                       
   1.438 +