lemon-project-template-glpk
diff deps/glpk/examples/train.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/train.mod Sun Nov 06 20:59:10 2011 +0100 1.3 @@ -0,0 +1,281 @@ 1.4 +# TRAIN, a model of railroad passenger car allocation 1.5 +# 1.6 +# References: 1.7 +# Robert Fourer, David M. Gay and Brian W. Kernighan, "A Modeling Language 1.8 +# for Mathematical Programming." Management Science 36 (1990) 519-554. 1.9 + 1.10 +### SCHEDULE SETS AND PARAMETERS ### 1.11 + 1.12 +set cities; 1.13 + 1.14 +set links within {c1 in cities, c2 in cities: c1 <> c2}; 1.15 + 1.16 + # Set of cities, and set of intercity links 1.17 + 1.18 +param last > 0 integer; # Number of time intervals in a day 1.19 + 1.20 +set times := 1..last; # Set of time intervals in a day 1.21 + 1.22 +set schedule within 1.23 + {c1 in cities, t1 in times, 1.24 + c2 in cities, t2 in times: (c1,c2) in links}; 1.25 + 1.26 + # Member (c1,t1,c2,t2) of this set represents 1.27 + # a train that leaves city c1 at time t1 1.28 + # and arrives in city c2 at time t2 1.29 + 1.30 +### DEMAND PARAMETERS ### 1.31 + 1.32 +param section > 0 integer; 1.33 + 1.34 + # Maximum number of cars in one section of a train 1.35 + 1.36 +param demand {schedule} > 0; 1.37 + 1.38 + # For each scheduled train: 1.39 + # the smallest number of cars that 1.40 + # can meet demand for the train 1.41 + 1.42 +param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]); 1.43 + 1.44 + # Minimum number of cars needed to meet demand 1.45 + 1.46 +param high {(c1,t1,c2,t2) in schedule} 1.47 + 1.48 + := max (2, min (ceil(2*demand[c1,t1,c2,t2]), 1.49 + section*ceil(demand[c1,t1,c2,t2]/section) )); 1.50 + 1.51 + # Maximum number of cars allowed on a train: 1.52 + # 2 if demand is for less than one car; 1.53 + # otherwise, lesser of 1.54 + # number of cars needed to hold twice the demand, and 1.55 + # number of cars in minimum number of sections needed 1.56 + 1.57 +### DISTANCE PARAMETERS ### 1.58 + 1.59 +param dist_table {links} >= 0 default 0.0; 1.60 + 1.61 +param distance {(c1,c2) in links} > 0 1.62 + := if dist_table[c1,c2] > 0 then dist_table[c1,c2] else dist_table[c2,c1]; 1.63 + 1.64 + # Inter-city distances: distance[c1,c2] is miles 1.65 + # between city c1 and city c2 1.66 + 1.67 +### VARIABLES ### 1.68 + 1.69 +var U 'cars stored' {cities,times} >= 0; 1.70 + 1.71 + # u[c,t] is the number of unused cars stored 1.72 + # at city c in the interval beginning at time t 1.73 + 1.74 +var X 'cars in train' {schedule} >= 0; 1.75 + 1.76 + # x[c1,t1,c2,t2] is the number of cars assigned to 1.77 + # the scheduled train that leaves c1 at t1 and 1.78 + # arrives in c2 at t2 1.79 + 1.80 +### OBJECTIVES ### 1.81 + 1.82 +minimize cars: 1.83 + sum {c in cities} U[c,last] + 1.84 + sum {(c1,t1,c2,t2) in schedule: t2 < t1} X[c1,t1,c2,t2]; 1.85 + 1.86 + # Number of cars in the system: 1.87 + # sum of unused cars and cars in trains during 1.88 + # the last time interval of the day 1.89 + 1.90 +minimize miles: 1.91 + sum {(c1,t1,c2,t2) in schedule} distance[c1,c2] * X[c1,t1,c2,t2]; 1.92 + 1.93 + # Total car-miles run by all scheduled trains in a day 1.94 + 1.95 +### CONSTRAINTS ### 1.96 + 1.97 +account {c in cities, t in times}: 1.98 + 1.99 + U[c,t] = U[c, if t > 1 then t-1 else last] + 1.100 + 1.101 + sum {(c1,t1,c,t) in schedule} X[c1,t1,c,t] - 1.102 + sum {(c,t,c2,t2) in schedule} X[c,t,c2,t2]; 1.103 + 1.104 + # For every city and time: 1.105 + # unused cars in the present interval must equal 1.106 + # unused cars in the previous interval, 1.107 + # plus cars just arriving in trains, 1.108 + # minus cars just leaving in trains 1.109 + 1.110 +satisfy {(c1,t1,c2,t2) in schedule}: 1.111 + 1.112 + low[c1,t1,c2,t2] <= X[c1,t1,c2,t2] <= high[c1,t1,c2,t2]; 1.113 + 1.114 + # For each scheduled train: 1.115 + # number of cars must meet demand, 1.116 + # but must not be so great that unnecessary 1.117 + # sections are run 1.118 + 1.119 +### DATA ### 1.120 + 1.121 +data; 1.122 + 1.123 +set cities := BO NY PH WA ; 1.124 + 1.125 +set links := (BO,NY) (NY,PH) (PH,WA) 1.126 + (NY,BO) (PH,NY) (WA,PH) ; 1.127 + 1.128 +param dist_table := [*,*] BO NY 232 1.129 + NY PH 90 1.130 + PH WA 135 ; 1.131 + 1.132 +param last := 48 ; 1.133 + 1.134 +param section := 14 ; 1.135 + 1.136 +set schedule := 1.137 + 1.138 + (WA,*,PH,*) 2 5 6 9 8 11 10 13 1.139 + 12 15 13 16 14 17 15 18 1.140 + 16 19 17 20 18 21 19 22 1.141 + 20 23 21 24 22 25 23 26 1.142 + 24 27 25 28 26 29 27 30 1.143 + 28 31 29 32 30 33 31 34 1.144 + 32 35 33 36 34 37 35 38 1.145 + 36 39 37 40 38 41 39 42 1.146 + 40 43 41 44 42 45 44 47 1.147 + 46 1 1.148 + 1.149 + (PH,*,NY,*) 1 3 5 7 9 11 11 13 1.150 + 13 15 14 16 15 17 16 18 1.151 + 17 19 18 20 19 21 20 22 1.152 + 21 23 22 24 23 25 24 26 1.153 + 25 27 26 28 27 29 28 30 1.154 + 29 31 30 32 31 33 32 34 1.155 + 33 35 34 36 35 37 36 38 1.156 + 37 39 38 40 39 41 40 42 1.157 + 41 43 42 44 43 45 44 46 1.158 + 45 47 47 1 1.159 + 1.160 + (NY,*,BO,*) 10 16 12 18 14 20 15 21 1.161 + 16 22 17 23 18 24 19 25 1.162 + 20 26 21 27 22 28 23 29 1.163 + 24 30 25 31 26 32 27 33 1.164 + 28 34 29 35 30 36 31 37 1.165 + 32 38 33 39 34 40 35 41 1.166 + 36 42 37 43 38 44 39 45 1.167 + 40 46 41 47 42 48 43 1 1.168 + 44 2 45 3 46 4 48 6 1.169 + 1.170 + (BO,*,NY,*) 7 13 9 15 11 17 12 18 1.171 + 13 19 14 20 15 21 16 22 1.172 + 17 23 18 24 19 25 20 26 1.173 + 21 27 22 28 23 29 24 30 1.174 + 25 31 26 32 27 33 28 34 1.175 + 29 35 30 36 31 37 32 38 1.176 + 33 39 34 40 35 41 36 42 1.177 + 37 43 38 44 39 45 40 46 1.178 + 41 47 43 1 45 3 47 5 1.179 + 1.180 + (NY,*,PH,*) 1 3 12 14 13 15 14 16 1.181 + 15 17 16 18 17 19 18 20 1.182 + 19 21 20 22 21 23 22 24 1.183 + 23 25 24 26 25 27 26 28 1.184 + 27 29 28 30 29 31 30 32 1.185 + 31 33 32 34 33 35 34 36 1.186 + 35 37 36 38 37 39 38 40 1.187 + 39 41 40 42 41 43 42 44 1.188 + 43 45 44 46 45 47 46 48 1.189 + 47 1 1.190 + 1.191 + (PH,*,WA,*) 1 4 14 17 15 18 16 19 1.192 + 17 20 18 21 19 22 20 23 1.193 + 21 24 22 25 23 26 24 27 1.194 + 25 28 26 29 27 30 28 31 1.195 + 29 32 30 33 31 34 32 35 1.196 + 33 36 34 37 35 38 36 39 1.197 + 37 40 38 41 39 42 40 43 1.198 + 41 44 42 45 43 46 44 47 1.199 + 45 48 46 1 47 2 ; 1.200 + 1.201 +param demand := 1.202 + 1.203 + [WA,*,PH,*] 2 5 .55 6 9 .01 8 11 .01 1.204 + 10 13 .13 12 15 1.59 13 16 1.69 1.205 + 14 17 5.19 15 18 3.55 16 19 6.29 1.206 + 17 20 4.00 18 21 5.80 19 22 3.40 1.207 + 20 23 4.88 21 24 2.92 22 25 4.37 1.208 + 23 26 2.80 24 27 4.23 25 28 2.88 1.209 + 26 29 4.33 27 30 3.11 28 31 4.64 1.210 + 29 32 3.44 30 33 4.95 31 34 3.73 1.211 + 32 35 5.27 33 36 3.77 34 37 4.80 1.212 + 35 38 3.31 36 39 3.89 37 40 2.65 1.213 + 38 41 3.01 39 42 2.04 40 43 2.31 1.214 + 41 44 1.52 42 45 1.75 44 47 1.88 1.215 + 46 1 1.05 1.216 + 1.217 + [PH,*,NY,*] 1 3 1.05 5 7 .43 9 11 .20 1.218 + 11 13 .21 13 15 .40 14 16 6.49 1.219 + 15 17 16.40 16 18 9.48 17 19 17.15 1.220 + 18 20 9.31 19 21 15.20 20 22 8.21 1.221 + 21 23 13.32 22 24 7.35 23 25 11.83 1.222 + 24 26 6.61 25 27 10.61 26 28 6.05 1.223 + 27 29 9.65 28 30 5.61 29 31 9.25 1.224 + 30 32 5.40 31 33 8.24 32 34 4.84 1.225 + 33 35 7.44 34 36 4.44 35 37 6.80 1.226 + 36 38 4.11 37 39 6.25 38 40 3.69 1.227 + 39 41 5.55 40 42 3.29 41 43 4.77 1.228 + 42 44 2.91 43 45 4.19 44 46 2.53 1.229 + 45 47 4.00 47 1 1.65 1.230 + 1.231 + [NY,*,BO,*] 10 16 1.23 12 18 3.84 14 20 4.08 1.232 + 15 21 1.47 16 22 2.96 17 23 1.60 1.233 + 18 24 2.95 19 25 1.71 20 26 2.81 1.234 + 21 27 1.77 22 28 2.87 23 29 1.84 1.235 + 24 30 2.95 25 31 1.91 26 32 3.12 1.236 + 27 33 1.93 28 34 3.31 29 35 2.00 1.237 + 30 36 3.40 31 37 2.08 32 38 3.41 1.238 + 33 39 2.69 34 40 4.45 35 41 2.32 1.239 + 36 42 3.40 37 43 1.80 38 44 2.63 1.240 + 39 45 1.52 40 46 2.23 41 47 1.25 1.241 + 42 48 1.79 43 1 .97 44 2 1.28 1.242 + 45 3 .48 46 4 .68 48 6 .08 1.243 + 1.244 + [BO,*,NY,*] 7 13 .03 9 15 1.29 11 17 4.59 1.245 + 12 18 2.56 13 19 3.92 14 20 2.37 1.246 + 15 21 3.81 16 22 2.24 17 23 3.51 1.247 + 18 24 2.13 19 25 3.28 20 26 2.05 1.248 + 21 27 3.15 22 28 1.99 23 29 3.09 1.249 + 24 30 1.93 25 31 3.19 26 32 1.91 1.250 + 27 33 3.21 28 34 1.85 29 35 3.21 1.251 + 30 36 1.71 31 37 3.04 32 38 2.08 1.252 + 33 39 3.13 34 40 1.96 35 41 2.53 1.253 + 36 42 1.43 37 43 2.04 38 44 1.12 1.254 + 39 45 1.71 40 46 .91 41 47 1.32 1.255 + 43 1 1.80 45 3 1.13 47 5 .23 1.256 + 1.257 + [NY,*,PH,*] 1 3 .04 12 14 4.68 13 15 5.61 1.258 + 14 16 3.56 15 17 5.81 16 18 3.81 1.259 + 17 19 6.31 18 20 4.07 19 21 7.33 1.260 + 20 22 4.55 21 23 7.37 22 24 4.73 1.261 + 23 25 7.61 24 26 4.92 25 27 7.91 1.262 + 26 28 5.19 27 29 8.40 28 30 5.53 1.263 + 29 31 9.32 30 32 5.51 31 33 10.33 1.264 + 32 34 9.21 33 35 18.95 34 36 11.23 1.265 + 35 37 16.85 36 38 7.29 37 39 10.89 1.266 + 38 40 5.41 39 41 8.21 40 42 4.52 1.267 + 41 43 6.99 42 44 3.92 43 45 6.21 1.268 + 44 46 3.44 45 47 5.17 46 48 2.55 1.269 + 47 1 1.24 1.270 + 1.271 + [PH,*,WA,*] 1 4 .20 14 17 4.49 15 18 3.53 1.272 + 16 19 2.67 17 20 3.83 18 21 3.01 1.273 + 19 22 4.12 20 23 3.15 21 24 4.67 1.274 + 22 25 3.20 23 26 4.23 24 27 2.87 1.275 + 25 28 3.84 26 29 2.60 27 30 3.80 1.276 + 28 31 2.77 29 32 4.31 30 33 3.16 1.277 + 31 34 4.88 32 35 3.45 33 36 5.55 1.278 + 34 37 3.52 35 38 6.11 36 39 3.32 1.279 + 37 40 5.53 38 41 3.03 39 42 4.51 1.280 + 40 43 2.53 41 44 3.39 42 45 1.93 1.281 + 43 46 2.52 44 47 1.20 45 48 1.75 1.282 + 46 1 .88 47 2 .87 ; 1.283 + 1.284 +end;