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