# GLPK/GMPL (MathProg)

< GLPK

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

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)

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.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

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

Here's the Transporation 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.

## 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 [2] provide an excellent introduction to coding in MathProg.

## References

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.