GLPK/GMPL (MathProg)

From Wikibooks, open books for an open world
< GLPK
Jump to: navigation, search

GNU MathProg is a high-level language for creating mathematical programming models. MathProg is specific to GLPK, but resembles a subset of AMPL[1]. MathProg can also be referred to as GMPL (GNU Mathematical Programming Language), the two terms being interchangeable.

Detailed examples can be found in the dedicated sub-pages beneath this page, grouped according to their problem domain. This page, in contrast, provides an overview and gives a short example.

Official documentation[edit]

The official GLPK documentation file doc/gmpl.pdf contains a full reference for the MathProg language. That material is therefore not repeated here. See obtaining GLPK.

Fourer, Gay, and Kernighan (2002)[edit]

Chapters from this classic book on the AMPL modeling language (second edition) are now downloadable: http://www.ampl.com/BOOK/download.html

Author Robert Fourer writes (August 2012): "Chapters 1–10 can also serve as an introduction to GMPL (GNU MathProg), though there are differences in the details."

Short example[edit]

The following MathProg example implements the linear constrained optimization model:

maximize 0.6 x_1 + 0.5 x_2\,
subject to x_1+2 x_2 \le 1
3 x_1 + x_2 \le 2

In this model, there is no requirement for x_1 and x_2 to be non-negative.

# short example
var x1;
var x2;
maximize obj: 0.6 * x1 + 0.5 * x2;
s.t. c1: x1 + 2 * x2 <= 1;
s.t. c2: 3 * x1 + x2 <= 2;
solve;
display x1, x2;
end;

To solve this model with GLPK, save the above text as short.mod and then invoke:

$ glpsol --math short.mod

You should obtain x_1 = 0.6 and x_2 = 0.2 as part of the terminal output from the GLPK solver.

The same model is coded using GLPK library calls (requires C programming). The same problem is shown in a number of problem formats.

Official GLPK examples[edit]

The examples directory in the official GLPK distribution contains about 60 MathProg (as well as some application programming) examples:

  • sample MathProg model (*.mod) files — with and without embedded data
  • sample MathProg data (*.dat) files — external data
  • sample database (*.dbf) files — table-based external data
  • sample data (*.csv) files — table-based external data

Note the instructions for downloading GLPK tarballs.

Very large models[edit]

Certain kinds of very large MathProg models can take a long time to parse, possibly hours. A large model might, for instance, comprise half a million graph edges. The GLPK MathProg translator is non-optimizing — meaning that it cannot recognize viable shortcuts during the parsing process. In some cases though, a MathProg model can be re-framed to work-around particular bottlenecks but the modeler will need to understand the mechanics of parsing first. In this May 2011 thread, GLPK author Andrew Makhorin suggests:

"The MathProg translator is not intended (by design) to process very large models. In such cases, it is better to use the GLPK API or to generate model data, for example in the GLPK LP format, with a specialized program or script." (grammar corrected)

That said, if the MathProg translator completes, then the resulting model will be satisfactory. Furthermore, the MathProg translator is not normally memory bound, so running a parse job overnight might provide an acceptable strategy.

Troubleshooting[edit]

If you encounter problems with your MathProg model, you can investigate further by specifying the GLPSOL options --nopresol to disable the LP presolver and --output filename.out to write the final solution to a text file.

If you receive the message "PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION", then hunt through the solution file for the variables that violate their bounds. This should allow you to identify which constraints are contradictory and the kinds of adjustment that might lead to a feasible system.

Background material[edit]

Tommi Sottinen’s course notes on operations research and GPLSOL [2] provide an excellent introduction to coding in MathProg.

References[edit]

  1. Fourer, Robert; Gay, David M.; Kernighan, Brian W. (2002). AMPL: a Modelling Language for Mathematical Programming (2 ed.). Duxbury. ISBN 0-534-38809-4. 
  2. Sottinen, Tommi (2009). Operations research with GNU Linear Programming Kit. ORMS1020 course notes. Department of Mathematics and Statistics, University of Vaasa, Finland. http://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdf.