glpk_faq.txt

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

  You can find benchmarks for some LP and MIP solvers such as CPLEX,      
  GLPK, lp_solve, and OSL on Hans Mittelmann's webpage at                 
  <http://plato.asu.edu/bench.html>.                                      


  Q. What are the differences between AMPL and GNU MathProg?              

  A. The subset of AMPL implemented in MathProg approximately corresponds 
  to AMPL status in 1990, because it is mainly based on the paper Robert  
  Fourer, David M Gay and Brian W Kernighan (1990), "A Modeling Language  
  for Mathematical Programming", Management Science, Vol 36, pp. 519-554  
  and is available at                                                     
  <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf>.                  

  The GNU MathProg translator was developed as part of GLPK. However, GNU 
  MathProg can be easily used in other applications as there is a set of  
  MathProg interface routines designed for use in other applications.     


  Q. What input file formats does GLPK support?                           

  A. GLPK presently can read input and output LP model files in three     
  supported formats:                                                      

    * MPS format - which is a column oriented and widely supported file       
      format but has poor human readability.                                  

    * CPLEX format - which is an easily readable row oriented format.         

    * GNU MathProg - which is an AMPL like mathematical modeling language.    


  Q. What interfaces are available for GLPK?                              

  A. The GLPK package is in fact a C API that can be either by statically 
  or dynamically linked directly with many programming systems.           

  Presently there are three contributed external interfaces included with 
  the GLPK package:                                                       

    * GLPK Java Native Interface (JNI)                                        

    * GLPK Delphi Interface (DELI)                                            

    * GLPKMEX Matlab MEX interface                                            

  There is an unofficial Microsoft Visual Basic, Tcl/Tk and Java GLPK     
  interface available at                                                  
  <http://gottfried.lindner.bei.t-online.de/glpk.htm>.                    

  There are other language interfaces under development, including a Perl 
  interface currently being developed by the FAQ maintainer, Dr. Harley   
  Mackenzie <[e-mail]>.                                       


  Q. Where can I find some examples?                                      

  A. The GLPK package distribution contains many examples written in GNU  
  MathProg (*.mod), C API calls (*.c), CPLEX input file format (*.lpt),   
  MPS format (*.mps) as well as some specific Traveling Salesman examples 
  (*.tsp).                                                                

  All of the examples can be found in the GLPK distribution examples      
  sub-directory.                                                          


  Q. What are the future plans for GLPK?                                  

  A. Developments planned for GLPK include improving the existing key     
  GLPK components, such as developing a more robust and more efficient    
  implementation of the simplex-based and interior-point solvers. Future  
  GLPK enhancements planned are implementing a branch-and-cut solver, a   
  MIP pre-processor, post-optimal and sensitivity analysis and possibly   
  network simplex and quadratic programming solvers.                      


  Q. How do I report a GLPK bug?                                          

  A. If you think you have found a bug in GLPK, then you should send as   
  complete a report as possible to <[e-mail]>.                    


  Q. How do I contribute to the GLPK development?                         

  A. At present new GLPK development patches should be emailed to Andrew  
  Makhorin <[e-mail] >, with sufficient documentation and test   
  code to explain the nature of the patch, how to install it and the      
  implications of its use. Before commencing any major GLPK development   
  for inclusion in the GLPK distribution, it would be a good idea to      
  discuss the idea on the GLPK mailing list.                              


  Q. How do I compile and link a GLPK application on a UNIX platform?     

  A. To compile a GLPK application on a UNIX platform, then compiler must 
  be able to include the GLPK include files and link to the GLPK library. 
  For example, on a system where the GLPK system is installed:            

  gcc mylp.c -o mylp -lglpk                                               

  or specify the include files and libglpk.a explicitly, if GLPK is not   
  installed.                                                              


  Q. How do I compile and link a GLPK application on a Win32 platform?    

  A. On a Win32 platform, GLPK is implemented either as a Win32 Dynamic   
  Link Library (DLL) or can be statically linked to the glpk*.lib file.   
  As with the UNIX instructions, a GLPK application must set a path to    
  the GLPK include files and also reference the GLPK library if           
  statically linked.                                                      


  Q. How do I limit the GLPK execution time?                              

  A. You can limit the computing time by setting the control parameter    
  LPX_K_TMLIM via the API routine lpx_set_real_parm . At present there is 
  no way of limiting the execution time of glpsol without changing the    
  source and recompiling a specific version.                              


GLPK Linear Programming

  Q. What is Linear Programming and how does it work?                     

  A. Linear Programming is a mathematical technique that is a generic     
  method for solving certain systems of equations with linear terms. The  
  real power of LP's are that they have many practical applications and   
  have proven to be a powerful and robust tool.                           

  The best single source of information on LP's is the Linear Programming 
  FAQ                                                                     
  <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html> 
  that has information on LP's and MIP's, includes a comprehensive list   
  of available LP software and has many LP references for further study.  


  Q. How do I determine the stability of an LP solution?                  

  A. You can perform sensitivity analysis by specifying the --bounds      
  option for glpsol as:                                                   

  glpsol ... --bounds filename                                            

  in which case the solver writes results of the analysis to the          
  specified filename in plain text format. The corresponding API routine  
  is lpx_print_sens_bnds() .                                              


  Q. How do I determine which constraints are causing infeasibility?      

  A straightforward way to find such a set of constraints is to drop      
  constraints one at a time. If dropping a constraint results in a        
  solvable problem, pick it up and go on to the next constraint. After    
  applying phase 1 to an infeasible problem, all basic satisfied          
  constraints may be dropped.                                             

  If the problem has a feasible dual, then running the dual simplex       
  method is a more direct approach. After the last pivot, the nonbasic    
  constraints and one of the violated constraints will constitute a       
  minimal set. The GLPK simplex table routines will allow you to pick a   
  correct constraint from the violated ones.                              

  Note that the GLPK pre-solver needs to be turned off for the preceding  
  technique to work, otherwise GLPK does not keep the basis of an         
  infeasible solution.                                                    

  Also a more detailed methodology has been posted on the mail list       
  archive at                                                              
  <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>.     


  Q. What is the difference between checks and constraints?               

  A. Check statements are intended to check that all data specified by    
  the user of the model are correct, mainly in the data section of a      
  MathProg model. For example, if some parameter means the number of      
  nodes in a network, it must be positive integer, that is just the       
  condition to be checked in the check statement (although in this case   
  such condition may be also checked directly in the parameter            
  statement). Note that check statements are performed when the           
  translator is generating the model, so they cannot include variables.   

  Constraints are conditions that are expressed in terms of variables and 
  resolved by the solver after the model has been completely generated.   
  If all data specified in the model are correct a priori, check          
  statements are not needed and can be omitted, while constraints are     
  essential components of the model and therefore cannot be omitted.      


GLPK Integer Programming 

  Q. What is Integer Programming and how does it work?                    

  A. Integer LP models are ones whose variables are constrained to take   
  integer or whole number (as opposed to fractional) values. It may not   
  be obvious that integer programming is a very much harder problem than  
  ordinary linear programming, but that is nonetheless the case, in both  
  theory and practice.                                                    


  Q. What is the Integer Optimization Suite (IOS)?                        

  A. IOS is a framework to implement implicit enumeration methods based   
  on LP relaxation (like branch-and-bound and branch-and-cut). Currently  
  IOS includes only basic features (the enumeration tree, API routines,   
  and the driver) and is not completely documented.                       


  Q. I have just changed an LP to a MIP and now it doesn't work?          

  A. If you have an existing LP that is working and you change to an MIP  
  and receive a "lpx_integer: optimal solution of LP relaxation required" 
  204 (==LPX_E_FAULT) error, you probably have not called the LP solution 
  method lpx_simplex() before lpx_integer() . The MIP routines use the LP 
  solution as part of the MIP solution methodology.