lemon-project-template-glpk
diff deps/glpk/examples/gap.mod @ 9:33de93886c88
Import GLPK 4.47
author | Alpar Juttner <alpar@cs.elte.hu> |
---|---|
date | Sun, 06 Nov 2011 20:59:10 +0100 |
parents | |
children |
line diff
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/deps/glpk/examples/gap.mod Sun Nov 06 20:59:10 2011 +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;