Thursday, September 1, 2011

Using glpsol (GNU Linear Program Solver)

Suppose you have a linear programming problem like:

maximize x1 - 3x2 + 9x3 -x4
such that:
x1 - 1.5x2 + 0.5x3 - x4 <=90
2x1 + x2 - x3 - x4 <= 15
-x1 -x2 + x3 - x4 <= 9
-x1 + x2 +4x3 - 5x4 <= 10

x1, x2, x3, x4 >= 0

It translates into the input for glpsol:
var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;


maximize z : x1 - (3 * x2) + (9 * x3) -x4;
s.t. x5 : x1 - (1.5 * x2) + (0.5 * x3) - x4 <=90;
s.t. x6 : (2 * x1) + x2 - x3 - x4 <= 15;
s.t. x7 : -x1 -x2 + x3 - x4 <= 9;
s.t. x8 : -x1 + x2 +(4 * x3) - (5 * x4) <= 10;


end;

Once your file is constructed to correctly represent the problem, simply execute glpsol on it:
glpsol -m problem.txt -o problem.out
This assumes that problem.txt is the file you just wrote; the output will be written to problem.out

This problem.out file looks like:
Problem:    problem
Rows:       5
Columns:    4
Non-zeros:  20
Status:     UNDEFINED
Objective:  z = 0 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 z            B              0
     2 x5           B              0                          90
     3 x6           B              0                          15
     4 x7           B              0                           9
     5 x8           B              0                          10

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                       < eps
     2 x2           NL             0             0                       < eps
     3 x3           NL             0             0                       < eps
     4 x4           NL             0             0                       < eps

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 = 9.00e+00 on column 3
        max.rel.err = 9.00e-01 on column 3
        DUAL SOLUTION IS WRONG

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

The objective function (z) has an optimum value of 0 (the yellow highlight).  The values of the x's are all 0 (because I made up this problem); the green highlight shows the x values.  Note that if an x doesn't show up in that section, it was an entering value at some point and never left to rejoin the basis.

No comments:

Post a Comment