glpk_faq.txt

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

GNU Linear Programming Kit FAQ

  Summary: Frequently Asked Questions about the GNU Linear Programming Kit

  Author: Dr. Harley Mackenzie <[e-mail]>                     

  Posting-Frequency: Monthly                                              

  Language: English                                                       

  $Date: 2004/01/09 05:57:57 $                                            

  $Revision: 1.6 $                                                        



Introduction

  Q. What is GPLK?                                                        

  A. GLPK stands for the GNU Linear Programming Kit. The GLPK package is  
  a set of routines written in ANSI C and organized in the form of a      
  callable library. This package is intended for solving large-scale      
  linear programming (LP), mixed integer linear programming (MIP), and    
  other related problems.                                                 

  The GLPK package includes the following main components:                

    * implementation of the simplex method,                                   

    * implementation of the primal-dual interior point method,                

    * implementation of the branch-and-bound method,                          

    * application program interface (API),                                    

    * GNU MathProg modeling language (a subset of AMPL),                      

    * GLPSOL, a stand-alone LP/MIP solver.                                    


  Q. Who develops and maintains GLPK?                                     

  A. GLPK is currently developed and maintained by Andrew Makhorin,       
  Department for Applied Informatics, Moscow Aviation Institute, Moscow,  
  Russia. Andrew's email address is <[e-mail]> and his postal    
  address is 125871, Russia, Moscow, Volokolamskoye sh., 4, Moscow        
  Aviation Institute, Andrew O. Makhorin                                  


  Q. How is GLPK licensed?                                                

  A. GLPK is currently licensed under the GNU General Public License      
  (GPL). GLPK is free software; you can redistribute it and/or modify it  
  under the terms of the GNU General Public License as published by the   
  Free Software Foundation; either version 2, or (at your option) any     
  later version.                                                          

  GLPK is not licensed under the Lesser General Public License (LGPL) as  
  distinct from other free LP codes such as lp_solve. The most            
  significant implication is that code that is linked to the GLPK library 
  must be released under the GPL, whereas with the LGPL, code linked to   
  the library does not have to be released under the same license.        


  Q. Where is the GLPK home page?                                         

  The GLPK home page is part of the GNU web site and can found at         
  <http://www.gnu.org/software/glpk/glpk.html>.                           


  Q. How do I download and install GLPK?                                  

  A. The GLPK source distribution can be found in the subdirectory        
  /gnu/glpk/ on your favorite GNU mirror                                  
  <http://www.gnu.org/prep/ftp.html> and can be compiled directly from    
  the source.                                                             

  The GLPK package (like all other GNU software) is distributed in the    
  form of packed archive. This is one file named 'glpk-x.y.tar.gz', where 
  x is the major version number and y is the minor version number.        

  In order to prepare the distribution for installation you should:       

    1. Copy the GLPK distribution file to some subdirectory.                   

    2. Enter the command 'gzip -d glpk-x.y.tar.gz' in order to unpack the      
       distribution file. After unpacking the name of the distribution file    
       will be automatically changed to 'glpk-x.y.tar'.                        

    3. Enter the command 'tar -x < glpk-x.y.tar' in order to unarchive the     
       distribution. After this operation the subdirectory 'glpk-x.y' which is 
       the GLPK distribution will have been automatically created.             

  After you have unpacked and unarchived GLPK distribution you should     
  configure the package, and compiled the application. The result of      
  compilation is:                                                         

    * the file 'libglpk.a', which is a library archive containing object code 
      for all GLPK routines; and                                              

    * the program 'glpsol', which is a stand-alone LP/MIP solver.             

  Complete compilation and installation instructions are included in the  
  INSTALL file included with the distribution.                            

  The distribution includes make files for the Microsoft Visual C/C++     
  version 6 and Borland C/C++ version 5 and by default compiles and links 
  a glpk*.lib library file, a glpk*.dll DLL file and an glpsol.exe        
  application file. A GNU Windows 4.1 binary, source and documentation    
  compiled using the mingw32 C/C++ compiler is also available from        
  <http://gnuwin32.sourceforge.net/packages/glpk.htm>.                    


  Q. Is there a GLPK mailing list or newsgroup?                           

  A. GLPK has two mailing lists: <[e-mail]> and                  
  <[e-mail]>.                                                     

  The main discussion list is <[e-mail]>, and is used to discuss 
  all aspects of GLPK, including its development and porting. There is    
  also a special list used for reporting bugs at <[e-mail]>.      

  To subscribe to any GLPK mailing list, send an empty mail with a        
  Subject: header line of just "subscribe" to the relevant -request list. 
  For example, to subscribe yourself to the main list, you would send     
  mail to <[e-mail]> with no body and a Subject: header  
  line of just "subscribe".                                               

  Another way to subscribe to the GLP mailing lists is to visit the web   
  pages <http://mail.gnu.org/mailman/listinfo/help-glpk> and              
  <http://mail.gnu.org/mailman/listinfo/bug-glpk>.                        

  Currently there are no newsgroups dedicated to GLPK.                    


  Q. Who maintains this FAQ and how do I contribute to this FAQ?          

  A. The present maintainer of this FAQ is Dr. Harley Mackenzie, HARD     
  software, although the content of the FAQ is derived from many sources  
  such as GLPK documentation, GLPK email archives and original content.   

  Harley's email address is <[e-mail]> and his postal address 
  is c/o HARD software, PO Box 8004, Newtown, Victoria 3220, Australia.   

  All contributions to this FAQ, such as questions and (preferably)       
  answers should be sent to the <[e-mail]> email address.     
  This FAQ is copyright Harley Mackenzie 2003 and is released under the   
  same license, terms and conditions as GLPK, that is, GPL version 2 or   
  later.                                                                  

  Contributions are not directly referenced in the body of the FAQ as     
  this would become unmanageable and messy, but rather as a list of       
  contributors to this FAQ. If you are the author of any information      
  included in this FAQ and you do not want your content to be included,   
  please contact the FAQ maintainer and your material will be removed.    
  Also if you have not been correctly included as a contributor to this   
  FAQ, your details have changed, or you do not want your name listed in  
  the list of contributors, please contact the FAQ maintainer for         
  correction.                                                             


  Q. Where can I download this FAQ?                                       

  The latest version of the GLPK FAQ is available to download from        
  <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> in the following   
  formats:                                                                

    * DocBook                                                                 

    * Formatted text                                                          

    * Adobe PDF                                                               


  Q. Who are the FAQ contributors?                                        

  A. The FAQ contents were created from the following sources:            

    * Michael Hennebry                                                        

    * http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html   

    * Harley Mackenzie, HARD software Pty. Ltd.                               

    * Andrew Makhorin, Department for Applied Informatics, Moscow Aviation    
      Institute                                                               


GLPK functions & features

  Q. What is the current state of GLPK development?                       

  A. GLPK is a work in progress and is presently under continual          
  development. As of the current version 4.3, GLPK is a simplex-based     
  solver is able to handle problems with up to 100,000 constraints. In    
  particular, it successfully solves all instances from netlib (see the   
  file bench.txt included in the GLPK distribution). The interior-point   
  solver is not very robust as it is unable to handle dense columns,      
  sometimes terminates due to numeric instability or slow convergence.    

  The Mixed Integer Programming (MIP) solver currently is based on        
  branch-and-bound, so it is unable to solve hard or very large problems  
  with a probable practical limit of 100-200 integer variables. However,  
  sometimes it is able to solve larger problems of up to 1000 integer     
  variables, although the size that depends on properties of particular   
  problem.                                                                


  Q. How does GLPK compare with other LP codes?                           

  A. I think that on very large-scale instances CPLEX 8.0 dual simplex is 
  10-100 times faster than the GLPK simplex solver and, of course, much   
  more robust. In many cases GLPK is faster and more robust than lp_solve 
  4.0 for pure LPs as well as MIP's. See the bench.txt file in the GLPK   
  distribution doc directory for GLPK netlib benchmark results.