1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/examples/gap.mod	Mon Dec 06 13:09:21 2010 +0100
     1.3 @@ -0,0 +1,79 @@
     1.4 +/* GAP, Generalized Assignment Problem */
     1.5 +
     1.6 +/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
     1.7 +
     1.8 +/* The Generalized Assignment Problem (GAP) is to assign a set of jobs
     1.9 +   to a set of agents subject to the constraints that each job must be
    1.10 +   assigned exactly to one agent and the total resources consumed by all
    1.11 +   jobs assigned to an agent must not exceed the agent's capacity. */
    1.12 +
    1.13 +param m, integer, > 0;
    1.14 +/* number of agents */
    1.15 +
    1.16 +param n, integer, > 0;
    1.17 +/* number of jobs */
    1.18 +
    1.19 +set I := 1..m;
    1.20 +/* set of agents */
    1.21 +
    1.22 +set J := 1..n;
    1.23 +/* set of jobs */
    1.24 +
    1.25 +param a{i in I, j in J}, >= 0;
    1.26 +/* resource consumed in allocating job j to agent i */
    1.27 +
    1.28 +param b{i in I}, >= 0;
    1.29 +/* resource capacity of agent i */
    1.30 +
    1.31 +param c{i in I, j in J}, >= 0;
    1.32 +/* cost of allocating job j to agent i */
    1.33 +
    1.34 +var x{i in I, j in J}, binary;
    1.35 +/* x[i,j] = 1 means job j is assigned to agent i */
    1.36 +
    1.37 +s.t. one{j in J}: sum{i in I} x[i,j] = 1;
    1.38 +/* job j must be assigned exactly to one agent */
    1.39 +
    1.40 +s.t. lim{i in I}: sum{j in J} a[i,j] * x[i,j] <= b[i];
    1.41 +/* total amount of resources consumed by all jobs assigned to agent i
    1.42 +   must not exceed the agent's capacity */
    1.43 +
    1.44 +minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
    1.45 +/* the objective is to find cheapest assignment (note that gap can also
    1.46 +   be formulated as maximization problem) */
    1.47 +
    1.48 +data;
    1.49 +
    1.50 +/* These data correspond to the instance c515-1 (gap1) from:
    1.51 +
    1.52 +   I.H. Osman, "Heuristics for the Generalised Assignment Problem:
    1.53 +   Simulated Annealing and Tabu Search Approaches", OR Spektrum, Volume
    1.54 +   17, 211-225, 1995
    1.55 +
    1.56 +   D. Cattrysse, M. Salomon and L.N. Van Wassenhove, "A set partitioning
    1.57 +   heuristic for the generalized assignment problem", European Journal
    1.58 +   of Operational Research, Volume 72, 167-174, 1994 */
    1.59 +
    1.60 +/* The optimal solution is 261 (minimization) or 336 (maximization) */
    1.61 +
    1.62 +param m := 5;
    1.63 +
    1.64 +param n := 15;
    1.65 +
    1.66 +param a :  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 :=
    1.67 +      1    8 15 14 23  8 16  8 25  9 17 25 15 10  8 24
    1.68 +      2   15  7 23 22 11 11 12 10 17 16  7 16 10 18 22
    1.69 +      3   21 20  6 22 24 10 24  9 21 14 11 14 11 19 16
    1.70 +      4   20 11  8 14  9  5  6 19 19  7  6  6 13  9 18
    1.71 +      5    8 13 13 13 10 20 25 16 16 17 10 10  5 12 23 ;
    1.72 +
    1.73 +param b := 1 36, 2 34, 3 38, 4 27, 5 33;
    1.74 +
    1.75 +param c :  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 :=
    1.76 +      1   17 21 22 18 24 15 20 18 19 18 16 22 24 24 16
    1.77 +      2   23 16 21 16 17 16 19 25 18 21 17 15 25 17 24
    1.78 +      3   16 20 16 25 24 16 17 19 19 18 20 16 17 21 24
    1.79 +      4   19 19 22 22 20 16 19 17 21 19 25 23 25 25 25
    1.80 +      5   18 19 15 15 21 25 16 16 23 15 22 17 19 22 24 ;
    1.81 +
    1.82 +end;