lemon-project-template-glpk: deps/glpk/doc/glpk

lemon-project-template-glpk

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

Import GLPK 4.47

author	Alpar Juttner <alpar@cs.elte.hu>
date	Sun, 06 Nov 2011 20:59:10 +0100
parents
children

comparison

equal deleted inserted replaced

--1:000000000000
+:320dc29cb6b5
+GNU Linear Programming Kit FAQ
+Summary: Frequently Asked Questions about the GNU Linear Programming Kit
+Author: Dr. Harley Mackenzie <hjm@hardsoftware.com>
+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 <mao@mai2.rcnet.ru> 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: <help-glpk@gnu.org> and
+<bug-glpk@gnu.org>.
+The main discussion list is <help-glpk@gnu.org>, 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 <bug-glpk@gnu.org>.
+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 <help-glpk-request@gnu.org> 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 <hjm@hardsoftware.com> 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 <hjm@hardsoftware.com> 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.
+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 <hjm@hardsoftware.com>.
+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 <bug-glpk@gnu.org>.
+Q. How do I contribute to the GLPK development?
+A. At present new GLPK development patches should be emailed to Andrew
+Makhorin <mao@mai2.rcnet.ru >, 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.