alpar@1: /* GAP, Generalized Assignment Problem */
alpar@1: 
alpar@1: /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */
alpar@1: 
alpar@1: /* The Generalized Assignment Problem (GAP) is to assign a set of jobs
alpar@1:    to a set of agents subject to the constraints that each job must be
alpar@1:    assigned exactly to one agent and the total resources consumed by all
alpar@1:    jobs assigned to an agent must not exceed the agent's capacity. */
alpar@1: 
alpar@1: param m, integer, > 0;
alpar@1: /* number of agents */
alpar@1: 
alpar@1: param n, integer, > 0;
alpar@1: /* number of jobs */
alpar@1: 
alpar@1: set I := 1..m;
alpar@1: /* set of agents */
alpar@1: 
alpar@1: set J := 1..n;
alpar@1: /* set of jobs */
alpar@1: 
alpar@1: param a{i in I, j in J}, >= 0;
alpar@1: /* resource consumed in allocating job j to agent i */
alpar@1: 
alpar@1: param b{i in I}, >= 0;
alpar@1: /* resource capacity of agent i */
alpar@1: 
alpar@1: param c{i in I, j in J}, >= 0;
alpar@1: /* cost of allocating job j to agent i */
alpar@1: 
alpar@1: var x{i in I, j in J}, binary;
alpar@1: /* x[i,j] = 1 means job j is assigned to agent i */
alpar@1: 
alpar@1: s.t. one{j in J}: sum{i in I} x[i,j] = 1;
alpar@1: /* job j must be assigned exactly to one agent */
alpar@1: 
alpar@1: s.t. lim{i in I}: sum{j in J} a[i,j] * x[i,j] <= b[i];
alpar@1: /* total amount of resources consumed by all jobs assigned to agent i
alpar@1:    must not exceed the agent's capacity */
alpar@1: 
alpar@1: minimize obj: sum{i in I, j in J} c[i,j] * x[i,j];
alpar@1: /* the objective is to find cheapest assignment (note that gap can also
alpar@1:    be formulated as maximization problem) */
alpar@1: 
alpar@1: data;
alpar@1: 
alpar@1: /* These data correspond to the instance c515-1 (gap1) from:
alpar@1: 
alpar@1:    I.H. Osman, "Heuristics for the Generalised Assignment Problem:
alpar@1:    Simulated Annealing and Tabu Search Approaches", OR Spektrum, Volume
alpar@1:    17, 211-225, 1995
alpar@1: 
alpar@1:    D. Cattrysse, M. Salomon and L.N. Van Wassenhove, "A set partitioning
alpar@1:    heuristic for the generalized assignment problem", European Journal
alpar@1:    of Operational Research, Volume 72, 167-174, 1994 */
alpar@1: 
alpar@1: /* The optimal solution is 261 (minimization) or 336 (maximization) */
alpar@1: 
alpar@1: param m := 5;
alpar@1: 
alpar@1: param n := 15;
alpar@1: 
alpar@1: param a :  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 :=
alpar@1:       1    8 15 14 23  8 16  8 25  9 17 25 15 10  8 24
alpar@1:       2   15  7 23 22 11 11 12 10 17 16  7 16 10 18 22
alpar@1:       3   21 20  6 22 24 10 24  9 21 14 11 14 11 19 16
alpar@1:       4   20 11  8 14  9  5  6 19 19  7  6  6 13  9 18
alpar@1:       5    8 13 13 13 10 20 25 16 16 17 10 10  5 12 23 ;
alpar@1: 
alpar@1: param b := 1 36, 2 34, 3 38, 4 27, 5 33;
alpar@1: 
alpar@1: param c :  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 :=
alpar@1:       1   17 21 22 18 24 15 20 18 19 18 16 22 24 24 16
alpar@1:       2   23 16 21 16 17 16 19 25 18 21 17 15 25 17 24
alpar@1:       3   16 20 16 25 24 16 17 19 19 18 20 16 17 21 24
alpar@1:       4   19 19 22 22 20 16 19 17 21 19 25 23 25 25 25
alpar@1:       5   18 19 15 15 21 25 16 16 23 15 22 17 19 22 24 ;
alpar@1: 
alpar@1: end;