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

## Getting GLPK

• At Matfyz: You do not need to install anything, the command `glpsol` is available at every Linux desktop in the computer lab "Rotunda" at Malostranské náměstí.
• On Windows: Download the Windows binaries from the site http://winglpk.sourceforge.net/. Install it. After that, you can use the command line (`cmd.exe`) to launch `glpsol.exe`.
• On Linux: Use your favourite package manager. For instance, launch `sudo apt-get install glpk-utils`.
• On OS X: There are no easy-to-install binaries for OS X, but you can use homebrew -- see this guide for details.
• On the web: For small linear programs, or just for experimentation, you can try using the solver in JavaScript: Mathematical Programming in GNU MathProg. We do not recommend this version for large programs and for complex integer programming.

## 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) 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 > 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) then "is in the cover" else "is not used in the cover");
printf (if x > 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.