GLPK/GMPL (MathProg)

GNU MathProg is a high-level language for creating mathematical programming models. MathProg is specific to GLPK, but resembles a subset of AMPL. 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

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)

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

The following MathProg example implements the linear constrained optimization model:

maximize	$0.6x_{1}+0.5x_{2}\,$
subject to	$x_{1}+2x_{2}\leq 1$
	$3x_{1}+x_{2}\leq 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

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.

Here's the Transportation MathProg LP Model as part of the official GLPK/MathProg examples. There are three (3) components of the MathProg model, namely: (1) model, (2) data, and (3) report (i.e. post processing) - Optional.

# A TRANSPORTATION PROBLEM
#
# This problem finds a least cost shipping schedule that meets
# requirements at markets and supplies at factories.
#
#  References:
#              Dantzig G B, "Linear Programming and Extensions."
#              Princeton University Press, Princeton, New Jersey, 1963,
#              Chapter 3-3.

set I;
/* canning plants */

set J;
/* markets */

param a{i in I};
/* capacity of plant i in cases */

param b{j in J};
/* demand at market j in cases */

param d{i in I, j in J};
/* distance in thousands of miles */

param f;
/* freight in dollars per case per thousand miles */

param c{i in I, j in J} := f * d[i,j] / 1000;
/* transport cost in thousands of dollars per case */

var x{i in I, j in J} >= 0;
/* shipment quantities in cases */

minimize cost: sum{i in I, j in J} c[i,j] * x[i,j];
/* total transportation costs in thousands of dollars */

s.t. supply{i in I}: sum{j in J} x[i,j] <= a[i];
/* observe supply limit at plant i */

s.t. demand{j in J}: sum{i in I} x[i,j] >= b[j];
/* satisfy demand at market j */

solve;

# Report / Result Section (Optional)
printf '#################################\n';
printf 'Transportation Problem / LP Model Result\n';
printf '\n';
printf 'Minimum Cost = %.2f\n', cost;
printf '\n';

printf '\n';
printf 'Variables  (i.e. shipment quantities in cases ) \n';

printf 'Shipment quantities in cases\n';
printf 'Canning Plants  Markets   Solution (Cases) \n';
printf{i in I, j in J}:'%14s %10s %11s\n',i,j, x[i,j]; 
printf '\n';

printf 'Constraints\n';
printf '\n';
printf 'Observe supply limit at plant i\n';
printf 'Canning Plants Solution Sign  Required\n';
for {i in I} {
 printf '%14s %10.2f <= %.3f\n', i, sum {j in J} x[i,j], a[i];
   }

printf '\n';
printf 'Satisfy demand at market j\n';
printf 'Market Solution Sign  Required\n';
for {j in J} {
 printf '%5s %10.2f >= %.3f\n', j, sum {i in I} x[i,j], b[j];
   }

data;

set I := Seattle San-Diego;

set J := New-York Chicago Topeka;

param a := Seattle     350
           San-Diego   600;

param b := New-York    325
           Chicago     300
           Topeka      275;

param d :              New-York   Chicago   Topeka :=
           Seattle     2.5        1.7       1.8
           San-Diego   2.5        1.8       1.4  ;

param f := 90;

end;

Examples on various inputs and outputs (e.g. csv, excel and database (i.e.access (mdb) and SQlite) can be seen in this page [| 10 reasons why you might want to use GLPK..]

Very large models

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.

Slow model translation

Models have been successfully restructured to reduce their parsing time by two orders of magnitude (from around 15 hours to 9 minutes). The open source OSeMOSYS energy model was subject to a United Nations competition and produced just this result. The speed up involved replacing nested set traversals with flat traversals across sets containing tuples instead. The revised approach was made possible because of near one-to-one associations within the semantics of the original sets. In addition, other set traversals were replaced altogether by using attributes. The take-home message is that nested set iterations should be avoided where possible, as these greatly expand the dimensionality and size of the model space to be processed. Moreover, think carefully about how your problem instance is going to be constructed by the MathProg translator when designing and implementing your model.

Troubleshooting

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

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