Intro

This text is mainly aimed at the students of the Mathematical-Physical Faculty of Charles University in Prague. The goal is for them to learn the bare minimum the need to solve practical homework exercises in the course Optimization Methods. The text covers the language GNU MathProg that can be used to state linear programs for the solver glpsol from the GLPK library.

This tutorial is sometimes intentionally brief on syntax details. If something confuses you or is outright wrong, please email me. This tutorial is licensed under CC BY-SA.

Getting GLPK

My first linear program

As we have stated before, the goal of this tutorial is to learn glpsol, a standalone solver of the GLPK project. Before we can launch it, we need to have some code to present it. We will thus set up the linear program as a text file, which we will then pass to the solver.

The first thing every programmer needs are comments:

# this is a bash-style comment that works 
/* this is a multiline comment
in the C style that works also */

The base syntax of MathProg is the following: commands are separated by semicolons and empty space is ignored. At the end, we need to say the magic word end;

Let's learn the basics on an example task, like modelling this linear program:

max 3x + 5y - 2z
2x + 3z <= 5
2z - 3y <= 8
y >= 3
y <= 4
x,y,z >= 0

The variables are defined with the keyword var. First comes the name of the variable, then we can add some comma separated specification of the variable, such as lower or upper bounds (if we know them in advance). Or, we might want to specify that the variables is integral: in that case, we add the keyword integer or binary if the values are just 0 or 1.

We have some lower and upper bounds on y, so let's plug them in:

var x >= 0;
var y, >= 3, <= 4;
var z >= 0;

The target function can be written as a linear function of the variables with its own label (the label is not too relevant, so let us just make it obj). The label goes before the word maximize/minimize and the target function itself. We have:

maximize obj: 3*x + 5*y - 2*z;

The constraints have the syntax which you would expect, with one substantial requirement: every constraint has to have a unique label, written before the inequality itself and separated by a colon. The label can contain both letters and numbers.

Our sample task will therefore have the following constraints: 

p1: 2*x + 3*z <= 5;
p2: 2*z - 3*y <= 8;

Finally, let us tell the solver that we actually want to solve; the linear program. With all things in place, we have:

# My Little Elpee: Optimization is Magic
var x >= 0;
var y, >= 3, <= 4;
var z >= 0;
maximize obj: 3*x + 5*y - 2*z;
p1: 2*x + 3*z <= 5;
p2: 2*z - 3*y <= 8;
solve;
end;

We launch the solver by typing glpsol.exe -m file1.mod. The solver will output a log of the solving procedure and a brief summary (like OPTIMAL LP SOLUTION FOUND, PROBLEM HAS NO PRIMAL FEASIBLE SOLUTION or so).

If we want to see the entire optimal solution, we can either modify the code to output the relevant variables (see section The Joy of Output) or use the parameter -w result.txt, which outputs everything into said file.

Let's Automate

We will now see a couple of tricks that will make our linear programs short and sweet. Our new task will be the following:

Write an integer program finding the minimum vertex cover for a graph on 5 vertices
with the following edges:
  1 -- 2;
  1 -- 3;
  1 -- 4;
  2 -- 4;
  3 -- 5;
  2 -- 5;

A parameter (a.k.a. a constant) can be defined using the keyword param. The definition is similar to the variables, only this time we should specify the right value with the assignment sign :=. The number of vertices is a good parameter, so let's make it one:

param N := 5;

Using sets can make our programs much shorter, especially when dealing with graphs and other set systems. The term set in MathProg is slightly misleading; sets are only allowed to contain either single elements or k-tuples (and one set must contain only k-tuples of the same size). Regardless, the concept of sets is quite powerful and we will make good use of it.

We can for instance generate the set of all vertices {1,2,3,4,5}:

set Vertices := (1..N);

We will also define the set of all edges, here explicitly listed as ordered pairs. (The contents of a set should be either ordered tuples or singletons.)

set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),2,5)};

Once we have some sets like that, we can use them to define variables and constraints. If we want to use a set to generate something, we will use an iterative expression, which is of the form {i in Largeset}. Inside the iterated clause, we use x[i] or x[i,j,k], if we have a more complex set.

Let us use the set Vertices to define all vertex variables:

var x{i in Vertices}, >= 0, <= 1, integer;

For shorter rows with many variabes, we can use the sum expression. Notation is the same as with any iterative expression, and we use x[i] inside the sum itself. Our target function will make use of a sum, being: 

minimize obj: sum{i in Vertices} x[i];

Now we need to add a single constraint for each edge. It would be nice if MathProg contained some kind of a for loop, so we could add all constraints in one swoop. We cannot really use a for loop, but we can index the constraints by some set, namely the set of edges: 

condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;

We are done! The final integer program looks like this :

# A program for solving the minimum vertex cover problem.
param N := 5;
set Vertices := (1..N);
set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),(2,5)};
var x{i in Vertices}, >= 0, <= 1, integer;
minimize obj: sum{i in Vertices} x[i];
condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;
solve;
end;

The Joy of Output

Once glpsol finishes, it will either answer in one line or (depending on the parameters) it spits out the value of all variables and tightness of all constraints. In order to avoid detective work of finding out which variables and inequalities are interesting, we can write our own output functions.

We shall see this by modifying our previous integer program on vertex cover.

To write an output statement, we place the command printf between the solve; and end; statements. Printfs behaves like it does in the C programming language. The first parameter is a format string followed by a comma-separated list of values we want. Let's see how to output a plain string first:

printf "#OUTPUT:\n";

We can iterate printf just like we did with constraints, which is useful for vertices in our case:

printf{i in Vertices} "Vertex %d has value %d\n", i, x[i];

Since our integer program is now solved (remember, we are below the solve; comamnd) we can use the if expression inside the printf to make the output dependent on the values:

printf "Vertex 1 %s\n" ,
     (if (x[1] = 1) then "is in the cover" else "is not used in the cover");

The if expression is a curious beast in MathProg -- it is not a statement/command like set, var, for, printf, but it is an expression instead -- much like 3,"string", (1..8). Our code will evaluate based on the optimal value; either it will evaluate to this: 

printf "Vertex 1 %s\n" , "is in the cover";
or to this: 
printf "Vertex 1 %s\n" , "is not used in the cover";

We can use the if expression on the format string as well; it will help us to either output an empty string or a string with a specific value. The trick is that after expansion, we may have printf "",3, which is a correct statement that outputs "".

printf (if x[3] > 0 then "Vertex %d is in the cover\n" else ""), 3;

Let's add one more simple string at the end:

printf "#OUTPUT END.\n";

Our complete program follows:

# A chatty integer program for minimum vertex cover
param N := 5;
set Vertices := (1..N);
set Edges := {(1,2),(1,3),(1,4),(2,4),(3,5),(2,5)};
var x{i in Vertices}, >= 0, <= 1, integer;
minimize obj: sum{i in Vertices} x[i];
condition_edge{(i,j) in Edges}: x[i] + x[j] >= 1;
solve;
printf "#OUTPUT:\n";
printf{i in Vertices} "Vertex %d has value %d\n", i, x[i];
printf "Vertex 1 %s\n" ,
    (if (x[1] = 1) then "is in the cover" else "is not used in the cover");
printf (if x[3] > 0 then "Vertex %d is in the cover\n" else ""), 3;
printf "#OUTPUT END\n";
end;
And the output will contain, among other things: 
#OUTPUT:
Vertex 1 has value 1
Vertex 2 has value 1
Vertex 3 has value 0
Vertex 4 has value 0
Vertex 5 has value 1
Vertex 1 is in the cover
#OUTPUT END

What's next?

By now, you should have a rough idea about what MathProg is like. This means you can now try and write your own first linear program. It's probably not going to be syntactically correct on your first try, but I am sure you can fix it all using the examples above and the reference manual.

Don't forget: you can always write a program in your favourite language which generates the MathProg linear program itself. The solver can accept a linear program that is ugly however you want; all it needs is that it can be parsed. Most of the construction listed above can be omitted if you use a generator to prepare your linear program!

On the other hand, the language GNU MathProg is much more detailed than what you have seen here. If your goal is to have a short and elegant linear program, you can find a lot more tricks and commands in the reference manual.

Useful links