GLPK/Steps of GMPL File Processing

This page describes the steps that GLPK takes when processing a model written in GMPL (also known as MathProg).

Processing steps

GLPK solves a model in a series of steps.

Model section translation

The model section of the GMPL file is parsed and internal structures describing the different objects, such as variables, constraints, and expressions, are created. This phase is executed by the function glp_mpl_read_model.

Data section translation

The data section of the model file is used to initialize parameters and sets. If the data section is contained within the model file, this phase is executed by the function glp_mpl_read_model. If data files are (optionally) provided, this phase is executed by the function glp_mpl_read_data.

Model generation

In this phase, the statements and expressions of the model up to the GMPL solve statement, are evaluated. This phase is executed by the function glp_mpl_generate. Model generation can be computationally expensive and users should expect the process of generating large or complex models to take time.

The constraints themselves are normalized according to the following rules:

Original form	Standard form
$ax+b\geq cy+d$	$ax-cy\geq d-b$
$ax+b\leq cy+d$	$ax-cy\leq d-b$
$ax+b=cy+d\,\!$	$ax-cy=d-b\,\!$
$c\leq ax+b\leq d$	$c-b\leq ax\leq d-b$

Dual values are calculated using the standard form of the constraint. This implies that, in the following example, the dual value of c2 will take the opposite sign relative to the dual value of c1 for the otherwise equivalent constraint formulations:

s.t. c1 : 3 * z = 1;
s.t. c2 : 1 = 3 * z;

Care is therefore required when interpreting the dual values for nonstandard constraints. Conversely, good practice suggests using the standard forms where practical.

Model building

The problem instance for the solver is created. This phase is executed by the function glp_mpl_build_prob. This call will fail if not preceded by a call to glp_mpl_generate.

Solution

A solution is attempted by calling the appropriate solver: simplex, interior-point, or MIP.

Postsolving

The results of the solver call are transferred back to the GMPL variables and constraints. All statements after the solve statement in the model file are executed. This phase is executed by function glp_mpl_postsolve.

Further study

More details can be obtained by examining:

• function glp_main in implementation file src/glpapi19.c (as of GLPK 4.45)
• the example in chapter 3.2 Routines for processing MathProg models in doc/glpk.pdf from the source distribution.

Prescribed starts

It is not possible to specify a feasible (but possibly suboptimal) starting solution when using GLPSOL — but this feature is supported when programming with the GLPK API using the callback hook of the branch-and-cut algorithm.