• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

How to use GLPK

Contents

  • Installation
  • Assignment problem
  • See also

GLPK, the GNU Linear Programming Kit, is a piece of software which solves linear optimization problems. You only have to modell the problem.

Installation

sudo apt-get install glpk-utils libglpk-dev glpk-doc python-glpk

Assignment problem

The assignment problem

The following file is in the examples of GLPK. Save it as problem.mod:

param m, integer, > 0;
/* number of agents */

param n, integer, > 0;
/* number of tasks */

set I := 1..m;
/* set of agents */

set J := 1..n;
/* set of tasks */

param c{i in I, j in J}, >= 0;
/* cost of allocating task j to agent i */

var x{i in I, j in J}, >= 0;
/* x[i,j] = 1 means task j is assigned to agent i
   note that variables x[i,j] are binary, however, there is no need to
   declare them so due to the totally unimodular constraint matrix */

s.t. phi{i in I}: sum{j in J} x[i,j] <= 1;
/* each agent can perform at most one task */

s.t. psi{j in J}: sum{i in I} x[i,j] = 1;
/* each task must be assigned exactly to one agent */

minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
/* the objective is to find a cheapest assignment */

solve;

printf "\n";
printf "Agent  Task       Cost\n";
printf{i in I} "%5d %5d %10g\n", i, sum{j in J} j * x[i,j],
   sum{j in J} c[i,j] * x[i,j];
printf "----------------------\n";
printf "     Total: %10g\n", sum{i in I, j in J} c[i,j] * x[i,j];
printf "\n";

data;

/* These data correspond to an example from [Christofides]. */

/* Optimal solution is 76 */

param m := 8;

param n := 8;

param c : 1  2  3  4  5  6  7  8 :=
      1  13 21 20 12  8 26 22 11
      2  12 36 25 41 40 11  4  8
      3  35 32 13 36 26 21 13 37
      4  34 54  7  8 12 22 11 40
      5  21  6 45 18 24 34 12 48
      6  42 19 39 15 14 16 28 46
      7  16 34 38  3 34 40 22 24
      8  26 20  5 17 45 31 37 43 ;

end;

Now run it with

glpsol --model assignment.mod

You will see

GLPSOL: GLPK LP/MIP Solver, v4.57
Parameter(s) specified in the command line:
 --model assignment.mod
Reading model section from assignment.mod...
Reading data section from assignment.mod...
assignment.mod:60: warning: final NL missing before end of file
60 lines were read
Generating phi...
Generating psi...
Generating obj...
Model has been successfully generated
GLPK Simplex Optimizer, v4.57
17 rows, 64 columns, 192 non-zeros
Preprocessing...
16 rows, 64 columns, 128 non-zeros
Scaling...
 A: min|aij| =  1.000e+00  max|aij| =  1.000e+00  ratio =  1.000e+00
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 16
      0: obj =   2.240000000e+02 inf =   7.000e+00 (1)
     13: obj =   1.750000000e+02 inf =   0.000e+00 (0)
*    28: obj =   7.600000000e+01 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND
Time used:   0.0 secs
Memory used: 0.2 Mb (192291 bytes)

Agent  Task       Cost
    1     1         13
    2     8          8
    3     7         13
    4     5         12
    5     2          6
    6     6         16
    7     4          3
    8     3          5
----------------------
     Total:         76

Model has been successfully processed

See also

  • GLPK Documentation
  • BwInf 31.1, A2
  • IBM: Introduction to linear optimization, Intermediate problems in linear programming, Advanced problems and elegant solutions
  • WikiBook

Published

Feb 23, 2017
by Martin Thoma

Category

Code

Tags

  • Constraint-satisfaction 2
  • COP 3
  • CSP 3
  • GLPK 2
  • optimization 4

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor