lemon-project-template-glpk

annotate deps/glpk/examples/train.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 # TRAIN, a model of railroad passenger car allocation
alpar@9 2 #
alpar@9 3 # References:
alpar@9 4 # Robert Fourer, David M. Gay and Brian W. Kernighan, "A Modeling Language
alpar@9 5 # for Mathematical Programming." Management Science 36 (1990) 519-554.
alpar@9 6
alpar@9 7 ### SCHEDULE SETS AND PARAMETERS ###
alpar@9 8
alpar@9 9 set cities;
alpar@9 10
alpar@9 11 set links within {c1 in cities, c2 in cities: c1 <> c2};
alpar@9 12
alpar@9 13 # Set of cities, and set of intercity links
alpar@9 14
alpar@9 15 param last > 0 integer; # Number of time intervals in a day
alpar@9 16
alpar@9 17 set times := 1..last; # Set of time intervals in a day
alpar@9 18
alpar@9 19 set schedule within
alpar@9 20 {c1 in cities, t1 in times,
alpar@9 21 c2 in cities, t2 in times: (c1,c2) in links};
alpar@9 22
alpar@9 23 # Member (c1,t1,c2,t2) of this set represents
alpar@9 24 # a train that leaves city c1 at time t1
alpar@9 25 # and arrives in city c2 at time t2
alpar@9 26
alpar@9 27 ### DEMAND PARAMETERS ###
alpar@9 28
alpar@9 29 param section > 0 integer;
alpar@9 30
alpar@9 31 # Maximum number of cars in one section of a train
alpar@9 32
alpar@9 33 param demand {schedule} > 0;
alpar@9 34
alpar@9 35 # For each scheduled train:
alpar@9 36 # the smallest number of cars that
alpar@9 37 # can meet demand for the train
alpar@9 38
alpar@9 39 param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]);
alpar@9 40
alpar@9 41 # Minimum number of cars needed to meet demand
alpar@9 42
alpar@9 43 param high {(c1,t1,c2,t2) in schedule}
alpar@9 44
alpar@9 45 := max (2, min (ceil(2*demand[c1,t1,c2,t2]),
alpar@9 46 section*ceil(demand[c1,t1,c2,t2]/section) ));
alpar@9 47
alpar@9 48 # Maximum number of cars allowed on a train:
alpar@9 49 # 2 if demand is for less than one car;
alpar@9 50 # otherwise, lesser of
alpar@9 51 # number of cars needed to hold twice the demand, and
alpar@9 52 # number of cars in minimum number of sections needed
alpar@9 53
alpar@9 54 ### DISTANCE PARAMETERS ###
alpar@9 55
alpar@9 56 param dist_table {links} >= 0 default 0.0;
alpar@9 57
alpar@9 58 param distance {(c1,c2) in links} > 0
alpar@9 59 := if dist_table[c1,c2] > 0 then dist_table[c1,c2] else dist_table[c2,c1];
alpar@9 60
alpar@9 61 # Inter-city distances: distance[c1,c2] is miles
alpar@9 62 # between city c1 and city c2
alpar@9 63
alpar@9 64 ### VARIABLES ###
alpar@9 65
alpar@9 66 var U 'cars stored' {cities,times} >= 0;
alpar@9 67
alpar@9 68 # u[c,t] is the number of unused cars stored
alpar@9 69 # at city c in the interval beginning at time t
alpar@9 70
alpar@9 71 var X 'cars in train' {schedule} >= 0;
alpar@9 72
alpar@9 73 # x[c1,t1,c2,t2] is the number of cars assigned to
alpar@9 74 # the scheduled train that leaves c1 at t1 and
alpar@9 75 # arrives in c2 at t2
alpar@9 76
alpar@9 77 ### OBJECTIVES ###
alpar@9 78
alpar@9 79 minimize cars:
alpar@9 80 sum {c in cities} U[c,last] +
alpar@9 81 sum {(c1,t1,c2,t2) in schedule: t2 < t1} X[c1,t1,c2,t2];
alpar@9 82
alpar@9 83 # Number of cars in the system:
alpar@9 84 # sum of unused cars and cars in trains during
alpar@9 85 # the last time interval of the day
alpar@9 86
alpar@9 87 minimize miles:
alpar@9 88 sum {(c1,t1,c2,t2) in schedule} distance[c1,c2] * X[c1,t1,c2,t2];
alpar@9 89
alpar@9 90 # Total car-miles run by all scheduled trains in a day
alpar@9 91
alpar@9 92 ### CONSTRAINTS ###
alpar@9 93
alpar@9 94 account {c in cities, t in times}:
alpar@9 95
alpar@9 96 U[c,t] = U[c, if t > 1 then t-1 else last] +
alpar@9 97
alpar@9 98 sum {(c1,t1,c,t) in schedule} X[c1,t1,c,t] -
alpar@9 99 sum {(c,t,c2,t2) in schedule} X[c,t,c2,t2];
alpar@9 100
alpar@9 101 # For every city and time:
alpar@9 102 # unused cars in the present interval must equal
alpar@9 103 # unused cars in the previous interval,
alpar@9 104 # plus cars just arriving in trains,
alpar@9 105 # minus cars just leaving in trains
alpar@9 106
alpar@9 107 satisfy {(c1,t1,c2,t2) in schedule}:
alpar@9 108
alpar@9 109 low[c1,t1,c2,t2] <= X[c1,t1,c2,t2] <= high[c1,t1,c2,t2];
alpar@9 110
alpar@9 111 # For each scheduled train:
alpar@9 112 # number of cars must meet demand,
alpar@9 113 # but must not be so great that unnecessary
alpar@9 114 # sections are run
alpar@9 115
alpar@9 116 ### DATA ###
alpar@9 117
alpar@9 118 data;
alpar@9 119
alpar@9 120 set cities := BO NY PH WA ;
alpar@9 121
alpar@9 122 set links := (BO,NY) (NY,PH) (PH,WA)
alpar@9 123 (NY,BO) (PH,NY) (WA,PH) ;
alpar@9 124
alpar@9 125 param dist_table := [*,*] BO NY 232
alpar@9 126 NY PH 90
alpar@9 127 PH WA 135 ;
alpar@9 128
alpar@9 129 param last := 48 ;
alpar@9 130
alpar@9 131 param section := 14 ;
alpar@9 132
alpar@9 133 set schedule :=
alpar@9 134
alpar@9 135 (WA,*,PH,*) 2 5 6 9 8 11 10 13
alpar@9 136 12 15 13 16 14 17 15 18
alpar@9 137 16 19 17 20 18 21 19 22
alpar@9 138 20 23 21 24 22 25 23 26
alpar@9 139 24 27 25 28 26 29 27 30
alpar@9 140 28 31 29 32 30 33 31 34
alpar@9 141 32 35 33 36 34 37 35 38
alpar@9 142 36 39 37 40 38 41 39 42
alpar@9 143 40 43 41 44 42 45 44 47
alpar@9 144 46 1
alpar@9 145
alpar@9 146 (PH,*,NY,*) 1 3 5 7 9 11 11 13
alpar@9 147 13 15 14 16 15 17 16 18
alpar@9 148 17 19 18 20 19 21 20 22
alpar@9 149 21 23 22 24 23 25 24 26
alpar@9 150 25 27 26 28 27 29 28 30
alpar@9 151 29 31 30 32 31 33 32 34
alpar@9 152 33 35 34 36 35 37 36 38
alpar@9 153 37 39 38 40 39 41 40 42
alpar@9 154 41 43 42 44 43 45 44 46
alpar@9 155 45 47 47 1
alpar@9 156
alpar@9 157 (NY,*,BO,*) 10 16 12 18 14 20 15 21
alpar@9 158 16 22 17 23 18 24 19 25
alpar@9 159 20 26 21 27 22 28 23 29
alpar@9 160 24 30 25 31 26 32 27 33
alpar@9 161 28 34 29 35 30 36 31 37
alpar@9 162 32 38 33 39 34 40 35 41
alpar@9 163 36 42 37 43 38 44 39 45
alpar@9 164 40 46 41 47 42 48 43 1
alpar@9 165 44 2 45 3 46 4 48 6
alpar@9 166
alpar@9 167 (BO,*,NY,*) 7 13 9 15 11 17 12 18
alpar@9 168 13 19 14 20 15 21 16 22
alpar@9 169 17 23 18 24 19 25 20 26
alpar@9 170 21 27 22 28 23 29 24 30
alpar@9 171 25 31 26 32 27 33 28 34
alpar@9 172 29 35 30 36 31 37 32 38
alpar@9 173 33 39 34 40 35 41 36 42
alpar@9 174 37 43 38 44 39 45 40 46
alpar@9 175 41 47 43 1 45 3 47 5
alpar@9 176
alpar@9 177 (NY,*,PH,*) 1 3 12 14 13 15 14 16
alpar@9 178 15 17 16 18 17 19 18 20
alpar@9 179 19 21 20 22 21 23 22 24
alpar@9 180 23 25 24 26 25 27 26 28
alpar@9 181 27 29 28 30 29 31 30 32
alpar@9 182 31 33 32 34 33 35 34 36
alpar@9 183 35 37 36 38 37 39 38 40
alpar@9 184 39 41 40 42 41 43 42 44
alpar@9 185 43 45 44 46 45 47 46 48
alpar@9 186 47 1
alpar@9 187
alpar@9 188 (PH,*,WA,*) 1 4 14 17 15 18 16 19
alpar@9 189 17 20 18 21 19 22 20 23
alpar@9 190 21 24 22 25 23 26 24 27
alpar@9 191 25 28 26 29 27 30 28 31
alpar@9 192 29 32 30 33 31 34 32 35
alpar@9 193 33 36 34 37 35 38 36 39
alpar@9 194 37 40 38 41 39 42 40 43
alpar@9 195 41 44 42 45 43 46 44 47
alpar@9 196 45 48 46 1 47 2 ;
alpar@9 197
alpar@9 198 param demand :=
alpar@9 199
alpar@9 200 [WA,*,PH,*] 2 5 .55 6 9 .01 8 11 .01
alpar@9 201 10 13 .13 12 15 1.59 13 16 1.69
alpar@9 202 14 17 5.19 15 18 3.55 16 19 6.29
alpar@9 203 17 20 4.00 18 21 5.80 19 22 3.40
alpar@9 204 20 23 4.88 21 24 2.92 22 25 4.37
alpar@9 205 23 26 2.80 24 27 4.23 25 28 2.88
alpar@9 206 26 29 4.33 27 30 3.11 28 31 4.64
alpar@9 207 29 32 3.44 30 33 4.95 31 34 3.73
alpar@9 208 32 35 5.27 33 36 3.77 34 37 4.80
alpar@9 209 35 38 3.31 36 39 3.89 37 40 2.65
alpar@9 210 38 41 3.01 39 42 2.04 40 43 2.31
alpar@9 211 41 44 1.52 42 45 1.75 44 47 1.88
alpar@9 212 46 1 1.05
alpar@9 213
alpar@9 214 [PH,*,NY,*] 1 3 1.05 5 7 .43 9 11 .20
alpar@9 215 11 13 .21 13 15 .40 14 16 6.49
alpar@9 216 15 17 16.40 16 18 9.48 17 19 17.15
alpar@9 217 18 20 9.31 19 21 15.20 20 22 8.21
alpar@9 218 21 23 13.32 22 24 7.35 23 25 11.83
alpar@9 219 24 26 6.61 25 27 10.61 26 28 6.05
alpar@9 220 27 29 9.65 28 30 5.61 29 31 9.25
alpar@9 221 30 32 5.40 31 33 8.24 32 34 4.84
alpar@9 222 33 35 7.44 34 36 4.44 35 37 6.80
alpar@9 223 36 38 4.11 37 39 6.25 38 40 3.69
alpar@9 224 39 41 5.55 40 42 3.29 41 43 4.77
alpar@9 225 42 44 2.91 43 45 4.19 44 46 2.53
alpar@9 226 45 47 4.00 47 1 1.65
alpar@9 227
alpar@9 228 [NY,*,BO,*] 10 16 1.23 12 18 3.84 14 20 4.08
alpar@9 229 15 21 1.47 16 22 2.96 17 23 1.60
alpar@9 230 18 24 2.95 19 25 1.71 20 26 2.81
alpar@9 231 21 27 1.77 22 28 2.87 23 29 1.84
alpar@9 232 24 30 2.95 25 31 1.91 26 32 3.12
alpar@9 233 27 33 1.93 28 34 3.31 29 35 2.00
alpar@9 234 30 36 3.40 31 37 2.08 32 38 3.41
alpar@9 235 33 39 2.69 34 40 4.45 35 41 2.32
alpar@9 236 36 42 3.40 37 43 1.80 38 44 2.63
alpar@9 237 39 45 1.52 40 46 2.23 41 47 1.25
alpar@9 238 42 48 1.79 43 1 .97 44 2 1.28
alpar@9 239 45 3 .48 46 4 .68 48 6 .08
alpar@9 240
alpar@9 241 [BO,*,NY,*] 7 13 .03 9 15 1.29 11 17 4.59
alpar@9 242 12 18 2.56 13 19 3.92 14 20 2.37
alpar@9 243 15 21 3.81 16 22 2.24 17 23 3.51
alpar@9 244 18 24 2.13 19 25 3.28 20 26 2.05
alpar@9 245 21 27 3.15 22 28 1.99 23 29 3.09
alpar@9 246 24 30 1.93 25 31 3.19 26 32 1.91
alpar@9 247 27 33 3.21 28 34 1.85 29 35 3.21
alpar@9 248 30 36 1.71 31 37 3.04 32 38 2.08
alpar@9 249 33 39 3.13 34 40 1.96 35 41 2.53
alpar@9 250 36 42 1.43 37 43 2.04 38 44 1.12
alpar@9 251 39 45 1.71 40 46 .91 41 47 1.32
alpar@9 252 43 1 1.80 45 3 1.13 47 5 .23
alpar@9 253
alpar@9 254 [NY,*,PH,*] 1 3 .04 12 14 4.68 13 15 5.61
alpar@9 255 14 16 3.56 15 17 5.81 16 18 3.81
alpar@9 256 17 19 6.31 18 20 4.07 19 21 7.33
alpar@9 257 20 22 4.55 21 23 7.37 22 24 4.73
alpar@9 258 23 25 7.61 24 26 4.92 25 27 7.91
alpar@9 259 26 28 5.19 27 29 8.40 28 30 5.53
alpar@9 260 29 31 9.32 30 32 5.51 31 33 10.33
alpar@9 261 32 34 9.21 33 35 18.95 34 36 11.23
alpar@9 262 35 37 16.85 36 38 7.29 37 39 10.89
alpar@9 263 38 40 5.41 39 41 8.21 40 42 4.52
alpar@9 264 41 43 6.99 42 44 3.92 43 45 6.21
alpar@9 265 44 46 3.44 45 47 5.17 46 48 2.55
alpar@9 266 47 1 1.24
alpar@9 267
alpar@9 268 [PH,*,WA,*] 1 4 .20 14 17 4.49 15 18 3.53
alpar@9 269 16 19 2.67 17 20 3.83 18 21 3.01
alpar@9 270 19 22 4.12 20 23 3.15 21 24 4.67
alpar@9 271 22 25 3.20 23 26 4.23 24 27 2.87
alpar@9 272 25 28 3.84 26 29 2.60 27 30 3.80
alpar@9 273 28 31 2.77 29 32 4.31 30 33 3.16
alpar@9 274 31 34 4.88 32 35 3.45 33 36 5.55
alpar@9 275 34 37 3.52 35 38 6.11 36 39 3.32
alpar@9 276 37 40 5.53 38 41 3.03 39 42 4.51
alpar@9 277 40 43 2.53 41 44 3.39 42 45 1.93
alpar@9 278 43 46 2.52 44 47 1.20 45 48 1.75
alpar@9 279 46 1 .88 47 2 .87 ;
alpar@9 280
alpar@9 281 end;