lemon-project-template-glpk

annotate deps/glpk/examples/gap.mod @ 9:33de93886c88

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