GNU MathProg

GNU MathProg is a high-level mathematical modelling language designed for creating and solving linear programming (LP), mixed integer programming (MIP), and other related optimisation problems. It is a subset of the AMPL (A Mathematical Programming Language) and is primarily used with the GNU Linear Programming Kit (GLPK).

Overview

GNU MathProg provides a structured definition of data, decision variables, constraints, and objective functions. It allows users to describe complex optimisation problems in a human-readable form, separate from the solution algorithm. The language supports sets, parameters, variables, constraints, and objective functions, and offers features for reading external data and generating reports.

Because of its syntactical similarity to AMPL, MathProg enables easy transition to commercial solvers for larger or more complex problems, while maintaining compatibility with free and open-source software tools.

Features

Support for linear and mixed-integer linear programming
AMPL-like syntax for easy model formulation
Built-in data section for embedding problem data
Compatibility with GLPK for solving and analysis
Ability to import external data using table statements

Usage

MathProg models are typically written in .mod files (sometimes .mpl) and solved using the GLPK solver via the glpsol command-line tool, a desktop or online interface. The general command-line usage pattern is:

glpsol --math my-model.mod --data my-data.dat

MathProg is particularly suited for educational purposes, small-scale optimisation, and rapid prototyping of models before deployment in more robust optimisation environments.

Example

We want to maximise the profit of two products (A and B). The profit for one pallet of A is £80, and £100 for B. Both products rely on the same resources (time and materials). It takes two hours to produce one pallet of product A and four hours for B. The time is limited to 80 hours (per day). To produce one palette of A, we need 80 kg of material. Similarly, 60 kg of material is needed for one pallet of B. The common material for A and B is limited to 2400 kg. How many pallets of A and B must be produced to maximise the profit? The mathematical problem formulation is:

${\begin{aligned}&{\underset {x_{1},x_{2}}{\text{max}}}&&80x_{1}+100x_{2}\\&{\text{subject to}}&&\\&&&2x_{1}+4x_{2}\leq 80\\&&&80x_{1}+60x_{2}\leq 2400\\\end{aligned}}$

The advantage of the MathProg is its similarity to the mathematical formulation.

# decision variables
var x1; # product A
var x2; # product B

maximize pounds: 80*x1 + 100*x2; # objective

# constraints
s.t. hours:     2*x1 +  4*x2 <=   80;
s.t. material: 80*x1 + 60*x2 <= 2400;
solve;

# Output code
printf "The optimal production per day is:\n";
printf " %.1f pallets of product A,\n",x1; 
printf " %.1f pallets of product B \n",x2; 
printf "This will return a profit of %.2f pounds\n",pounds;
end;

This example demonstrates the similarity of the MathProg model to the mathematical formulation. It contains an output code section, allowing the formatted display of essential values such as the objective and optimal decision values. For instance, the above output code generates:

The optimal production per day is:
 24.0 pallets of product A,
 8.0 pallets of product B 
This will return a profit of 2720.00 pounds

History

GNU MathProg was developed as part of the GNU Linear Programming Kit (GLPK) by Andrew Makhorin.^[1] It serves as an interface for users who prefer a declarative style of optimisation modelling without delving into the C API of GLPK.

External links

References

^ Makhorin, Andrew (2008). "Modeling Language GNU MathProg" (PDF). Moscow Aviation Institute. 63.

[Makhorin2008-1] Makhorin, Andrew (2008). "Modeling Language GNU MathProg" (PDF). Moscow Aviation Institute. 63.

[1]