GMPL model of motivational examples
Simple GMPL models of the motivational examples
- Prerequisites GMPL/glpk basics Linear Programming: first steps
Festivals example
The final mathematical model for the Festivals example looked like this:
\[ \begin{array}{rcl} y_1+y_3+y_4 &\ge& 1 \\ y_1+y_2+y_3+y_5 &\ge& 1 \\ y_1+y_2+y_4+y_5 &\ge& 1 \\ y_3+y_5 &\ge& 1 \\ y_4 &\ge& 1\\ y_2+y_3+y_4+y_5 &\ge& 1 \\ y_3+y_5 &\ge& 1 \\ \end{array} \]
\[ y_1+y_2+y_3+y_4+y_5 \to min\]
Let's see step by step, how this can be formulated in GMPL:
| Mathematical notation | GMPL code |
|---|---|
| Variables | |
| \(y_1,y_2,y_3,y_4,y_5 \in \{0,1\} \) | var y1 binary; |
var y2 binary; | |
var y3 binary; | |
var y4 binary; | |
var y5 binary; | |
| Constraints | |
| \( y_1+y_3+y_4 \ge 1 \) | s.t. Haggard: y1 + y3 + y4 >= 1; |
| \( y_1+y_2+y_3+y_5 \ge 1 \) | s.t. Stratovarius: y1 + y2 + y3 + y5 >= 1; |
| \( y_1+y_2+y_4+y_5 \ge 1 \) | s.t. Epica: y1 + y2 + y4 + y5 >= 1; |
| \( y_3+y_4 \ge 1 \) | s.t. Dalriada: y3 + y4 >= 1; |
| \( y_4 \ge 1 \) | s.t. Apocalyptica: y4 >= 1; |
| \( y_2+y_3+y_4+y_4+y_5 \ge 1 \) | s.t. Liva: y2 + y3 + y4 +y5 >= 1; |
| \( y_3+y_5 \ge 1 \) | s.t. Eluveitie: y3 + y5 >= 1; |
| Objective function | |
| \( y_1+y_2+y_3+y_4+y_5 \to min \) | minimize NumberOfFestivals: y1 + y2 + y3 + y4 + y5; |
Let's have a look at the ouptut:
Problem: froccs
Rows: 8
Columns: 5 (5 integer, 5 binary)
Non-zeros: 25
Status: INTEGER OPTIMAL
Objective: NumberOfFestivals = 2 (MINimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 Haggard 2 1
2 Stratovarius 1 1
3 Epica 1 1
4 Dalriada 2 1
5 Apocalyptica 1 1
6 Liva 2 1
7 Eluveitie 1 1
8 NumberOfFestivals
2
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 y1 * 0 0 1
2 y2 * 0 0 1
3 y3 * 1 0 1
4 y4 * 1 0 1
5 y5 * 0 0 1
Integer feasibility conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
End of output
From the line Status: INTEGER OPTIMAL we know that the solver managed to find the optimal solution.
From the line Objective: NumberOfFestivals = 2 (MINimum) we also know that the optimal number of festivals is 2.
We have to scroll down to the second table, to find out, that this could be achieved when the value of y3 and y4 is 1, and all of the other variables take the value of zero.
This means, that we need to go to only the third and fourth festivals.
Fröccs example
Similarly to the above example, we have already constructed the following LP model for the fröccs problem:
\[1 \cdot x_{KF} + 2 \cdot x_{NF}\ + 1 \cdot x_{HL} + 3 \cdot x_{HM} + 2 \cdot x_{VHM} + 9 \cdot x_{KrF} + 1 \cdot x_{SF} + 6 \cdot x_{PF} \le 1000\] \[1 \cdot x_{KF} + 1 \cdot x_{NF}\ + 2 \cdot x_{HL} + 2 \cdot x_{HM} + 3 \cdot x_{VHM} + 1 \cdot x_{KrF} + 9 \cdot x_{SF} + 3 \cdot x_{PF} \le 1500\]
\[110 \cdot x_{KF} + 200 \cdot x_{NF}\ + 120 \cdot x_{HL} + 260 \cdot x_{HM} + 200 \cdot x_{VHM} + 800 \cdot x_{KrF} + 200 \cdot x_{SF} + 550 \cdot x_{PF} \to max\]
Again, let's implement that in GMPL step by step:
| Mathematical notation | GMPL code |
|---|---|
| Variables | |
| \( x_{KF},x_{NF},x_{HL},x_{HM},x_{VHM},x_{KrF},x_{SF},x_{PF} \in [0,\infty[ \) | var xKF >=0; |
var xNF >=0; | |
var xHL >=0; | |
var xHM >=0; | |
var xVHM >=0; | |
var xKrF >=0; | |
var xSF >=0; | |
var xPF >=0; | |
| Constraints | |
| \( 1 \cdot x_{KF} + 2 \cdot x_{NF} + 1 \cdot x_{HL} + 3 \cdot x_{HM} + 2 \cdot x_{VHM} + 9 \cdot x_{KrF} + 1 \cdot x_{SF} + 6 \cdot x_{PF} \le 1000 \) | s.t. Wine: 1*xKF + 2*xNF + 1*xHL + 3*xHM + 2*xVHM + 9*xKrF + 1*xSF + 6*xPF <= 1000; |
| \( 1 \cdot x_{KF} + 1 \cdot x_{NF}\ + 2 \cdot x_{HL} + 2 \cdot x_{HM} + 3 \cdot x_{VHM} + 1 \cdot x_{KrF} + 9 \cdot x_{SF} + 3 \cdot x_{PF} \le 1500 \) | s.t. Soda: 1*xKF + 1*xNF + 2*xHL + 2*xHM + 3*xVHM + 1*xKrF + 9*xSF + 3*xPF <= 1500; |
| Objective function | |
| \( 110 \cdot x_{KF} + 200 \cdot x_{NF}\ + 120 \cdot x_{HL} + 260 \cdot x_{HM} + 200 \cdot x_{VHM} + 800 \cdot x_{KrF} + 200 \cdot x_{SF} + 550 \cdot x_{PF} \to max\) | maximize TotalIncome: 110*xKF + 200*xNF + 120*xHL + 260*xHM + 200*xVHM + 800*xKrF + 200*xSF + 550*xPF; |
Again, let's have a look at the ouptut:
Problem: froccs
Rows: 3
Columns: 8
Non-zeros: 24
Status: OPTIMAL
Objective: TotalIncome = 115625 (MAXimum)
No. Row name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 Wine NU 1000 1000 98.75
2 Soda NU 1500 1500 11.25
3 TotalIncome B 115625
No. Column name St Activity Lower bound Upper bound Marginal
------ ------------ -- ------------- ------------- ------------- -------------
1 xKF B 937.5 0
2 xNF NL 0 0 -8.75
3 xHL NL 0 0 -1.25
4 xHM NL 0 0 -58.75
5 xVHM NL 0 0 -31.25
6 xKrF NL 0 0 -100
7 xSF B 62.5 0
8 xPF NL 0 0 -76.25
Karush-Kuhn-Tucker optimality conditions:
KKT.PE: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.PB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
KKT.DE: max.abs.err = 0.00e+00 on column 0
max.rel.err = 0.00e+00 on column 0
High quality
KKT.DB: max.abs.err = 0.00e+00 on row 0
max.rel.err = 0.00e+00 on row 0
High quality
End of output
From the line Status: OPTIMAL we know that the solver managed to find the optimal solution.
Note, that the word "INTEGER" is missing, as we had no discrete variables, this model is "just" and LP, not an MILP.
From the line Objective: TotalIncome = 115625 (MAXimum) we also know that the maximal income we can have is 115625.
We have to scroll down to the second table, to find out, that this could be achieved by selling 937.5 portions of kisfröccs, and 62.5 portions of sóherfröccs.
Let's make mistakes!
Regardless of the programming or modelling language, small syntax mistakes are regularly made by beginners and experienced users alike. The only difference is, that those, who have a lot of practice, can correct those small mistakes quickly and easily, while beginners can spend a lot of time on this instead of focusing on the "essence" (semantics) of the model. The parsers usually provide more useful error messages instead of "Your input is incorrect.", but still, sometimes the message seems to have nothing to do with the actual problem.
A good practice is to find out these messages in a "safe environment". By this I mean, that if You have a perfect code, make small mistakes to it on purpose, and then look at the error message You get. This way You can easily make the connection between error messages and the types of mistakes that can be made. A bonus benefit of this approach is, that You know You have only done a single mistake, and the error messages are not the results of the combination of a few mistypos.
Some typical mistakes that You should check are:
- Missing semicolon at the end of variable declaration/constraint/objective function
- Missing the
s.t., or mistyping it somehow, likest.. - Some countries use a decimal comma instead of a dot, try to give numbers like that.
- Writing
<instead of<= - Trying to declare varianles in a single line, i.e.,
var x1,x2 >=0; - Putting semicolon instead of a colon, or the other way around.
- Forgetting the semicolon after the name of the constraint or objective function name, or using equal instead in the latter case.
- Using non-ascii characters for names, or names starting with numbers.
- Check if the names are case-sensitive or not? (I.e.,
var xKF;andvar Xkf;would collide or not?) - If it is case-sensitive, check the error message if You use the variable with incorrect spelling in the constraint/objective function.
- ...