train.mod

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

# TRAIN, a model of railroad passenger car allocation
#
# References:
# Robert Fourer, David M. Gay and Brian W. Kernighan, "A Modeling Language
# for Mathematical Programming." Management Science 36 (1990) 519-554.

###  SCHEDULE SETS AND PARAMETERS  ###

set cities;

set links within {c1 in cities, c2 in cities: c1 <> c2};

                        # Set of cities, and set of intercity links

param last > 0 integer; # Number of time intervals in a day

set times := 1..last;   # Set of time intervals in a day

set schedule within
      {c1 in cities, t1 in times,
       c2 in cities, t2 in times: (c1,c2) in links};

                        # Member (c1,t1,c2,t2) of this set represents
                        # a train that leaves city c1 at time t1
                        # and arrives in city c2 at time t2

###  DEMAND PARAMETERS  ###

param section > 0 integer;

                        # Maximum number of cars in one section of a train

param demand {schedule} > 0;

                        # For each scheduled train:
                        # the smallest number of cars that
                        # can meet demand for the train

param low {(c1,t1,c2,t2) in schedule} := ceil(demand[c1,t1,c2,t2]);

                        # Minimum number of cars needed to meet demand

param high {(c1,t1,c2,t2) in schedule}

   := max (2, min (ceil(2*demand[c1,t1,c2,t2]),
                   section*ceil(demand[c1,t1,c2,t2]/section) ));

                        # Maximum number of cars allowed on a train:
                        # 2 if demand is for less than one car;
                        # otherwise, lesser of
                        # number of cars needed to hold twice the demand, and
                        # number of cars in minimum number of sections needed

###  DISTANCE PARAMETERS  ###

param dist_table {links} >= 0 default 0.0;

param distance {(c1,c2) in links} > 0
   := if dist_table[c1,c2] > 0 then dist_table[c1,c2] else dist_table[c2,c1];

                        # Inter-city distances: distance[c1,c2] is miles
                        # between city c1 and city c2

###  VARIABLES  ###

var U 'cars stored' {cities,times} >= 0;

                        # u[c,t] is the number of unused cars stored
                        # at city c in the interval beginning at time t

var X 'cars in train' {schedule} >= 0;

                        # x[c1,t1,c2,t2] is the number of cars assigned to
                        # the scheduled train that leaves c1 at t1 and
                        # arrives in c2 at t2

###  OBJECTIVES  ###

minimize cars:
       sum {c in cities} U[c,last] +
       sum {(c1,t1,c2,t2) in schedule: t2 < t1} X[c1,t1,c2,t2];

                        # Number of cars in the system:
                        # sum of unused cars and cars in trains during
                        # the last time interval of the day

minimize miles:
       sum {(c1,t1,c2,t2) in schedule} distance[c1,c2] * X[c1,t1,c2,t2];

                        # Total car-miles run by all scheduled trains in a day

###  CONSTRAINTS  ###

account {c in cities, t in times}:

  U[c,t] = U[c, if t > 1 then t-1 else last] +

      sum {(c1,t1,c,t) in schedule} X[c1,t1,c,t] -
      sum {(c,t,c2,t2) in schedule} X[c,t,c2,t2];

                        # For every city and time:
                        # unused cars in the present interval must equal
                        # unused cars in the previous interval,
                        # plus cars just arriving in trains,
                        # minus cars just leaving in trains

satisfy {(c1,t1,c2,t2) in schedule}:

       low[c1,t1,c2,t2] <= X[c1,t1,c2,t2] <= high[c1,t1,c2,t2];

                        # For each scheduled train:
                        # number of cars must meet demand,
                        # but must not be so great that unnecessary
                        # sections are run

###  DATA  ###

data;

set cities := BO NY PH WA ;

set links := (BO,NY) (NY,PH) (PH,WA)
             (NY,BO) (PH,NY) (WA,PH) ;

param dist_table := [*,*]  BO NY  232
                           NY PH   90
                           PH WA  135 ;

param last := 48 ;

param section := 14 ;

set schedule :=

   (WA,*,PH,*)   2  5     6  9     8 11    10 13
                12 15    13 16    14 17    15 18
                16 19    17 20    18 21    19 22
                20 23    21 24    22 25    23 26
                24 27    25 28    26 29    27 30
                28 31    29 32    30 33    31 34
                32 35    33 36    34 37    35 38
                36 39    37 40    38 41    39 42
                40 43    41 44    42 45    44 47
                46  1

   (PH,*,NY,*)   1  3     5  7     9 11    11 13
                13 15    14 16    15 17    16 18
                17 19    18 20    19 21    20 22
                21 23    22 24    23 25    24 26
                25 27    26 28    27 29    28 30
                29 31    30 32    31 33    32 34
                33 35    34 36    35 37    36 38
                37 39    38 40    39 41    40 42
                41 43    42 44    43 45    44 46
                45 47    47  1

   (NY,*,BO,*)  10 16    12 18    14 20    15 21
                16 22    17 23    18 24    19 25
                20 26    21 27    22 28    23 29
                24 30    25 31    26 32    27 33
                28 34    29 35    30 36    31 37
                32 38    33 39    34 40    35 41
                36 42    37 43    38 44    39 45
                40 46    41 47    42 48    43  1
                44  2    45  3    46  4    48  6

   (BO,*,NY,*)   7 13     9 15    11 17    12 18
                13 19    14 20    15 21    16 22
                17 23    18 24    19 25    20 26
                21 27    22 28    23 29    24 30
                25 31    26 32    27 33    28 34
                29 35    30 36    31 37    32 38
                33 39    34 40    35 41    36 42
                37 43    38 44    39 45    40 46
                41 47    43  1    45  3    47  5

   (NY,*,PH,*)   1  3    12 14    13 15    14 16
                15 17    16 18    17 19    18 20
                19 21    20 22    21 23    22 24
                23 25    24 26    25 27    26 28
                27 29    28 30    29 31    30 32
                31 33    32 34    33 35    34 36
                35 37    36 38    37 39    38 40
                39 41    40 42    41 43    42 44
                43 45    44 46    45 47    46 48
                47  1

   (PH,*,WA,*)   1  4    14 17    15 18    16 19
                17 20    18 21    19 22    20 23
                21 24    22 25    23 26    24 27
                25 28    26 29    27 30    28 31
                29 32    30 33    31 34    32 35
                33 36    34 37    35 38    36 39
                37 40    38 41    39 42    40 43
                41 44    42 45    43 46    44 47
                45 48    46  1    47  2    ;

param demand :=

 [WA,*,PH,*]   2  5    .55      6  9    .01      8 11    .01
              10 13    .13     12 15   1.59     13 16   1.69
              14 17   5.19     15 18   3.55     16 19   6.29
              17 20   4.00     18 21   5.80     19 22   3.40
              20 23   4.88     21 24   2.92     22 25   4.37
              23 26   2.80     24 27   4.23     25 28   2.88
              26 29   4.33     27 30   3.11     28 31   4.64
              29 32   3.44     30 33   4.95     31 34   3.73
              32 35   5.27     33 36   3.77     34 37   4.80
              35 38   3.31     36 39   3.89     37 40   2.65
              38 41   3.01     39 42   2.04     40 43   2.31
              41 44   1.52     42 45   1.75     44 47   1.88
              46  1   1.05

 [PH,*,NY,*]   1  3   1.05      5  7    .43      9 11    .20
              11 13    .21     13 15    .40     14 16   6.49
              15 17  16.40     16 18   9.48     17 19  17.15
              18 20   9.31     19 21  15.20     20 22   8.21
              21 23  13.32     22 24   7.35     23 25  11.83
              24 26   6.61     25 27  10.61     26 28   6.05
              27 29   9.65     28 30   5.61     29 31   9.25
              30 32   5.40     31 33   8.24     32 34   4.84
              33 35   7.44     34 36   4.44     35 37   6.80
              36 38   4.11     37 39   6.25     38 40   3.69
              39 41   5.55     40 42   3.29     41 43   4.77
              42 44   2.91     43 45   4.19     44 46   2.53
              45 47   4.00     47 1    1.65

 [NY,*,BO,*]  10 16   1.23     12 18   3.84     14 20   4.08
              15 21   1.47     16 22   2.96     17 23   1.60
              18 24   2.95     19 25   1.71     20 26   2.81
              21 27   1.77     22 28   2.87     23 29   1.84
              24 30   2.95     25 31   1.91     26 32   3.12
              27 33   1.93     28 34   3.31     29 35   2.00
              30 36   3.40     31 37   2.08     32 38   3.41
              33 39   2.69     34 40   4.45     35 41   2.32
              36 42   3.40     37 43   1.80     38 44   2.63
              39 45   1.52     40 46   2.23     41 47   1.25
              42 48   1.79     43  1    .97     44  2   1.28
              45  3    .48     46  4    .68     48  6    .08

 [BO,*,NY,*]   7 13    .03      9 15   1.29     11 17   4.59
              12 18   2.56     13 19   3.92     14 20   2.37
              15 21   3.81     16 22   2.24     17 23   3.51
              18 24   2.13     19 25   3.28     20 26   2.05
              21 27   3.15     22 28   1.99     23 29   3.09
              24 30   1.93     25 31   3.19     26 32   1.91
              27 33   3.21     28 34   1.85     29 35   3.21
              30 36   1.71     31 37   3.04     32 38   2.08
              33 39   3.13     34 40   1.96     35 41   2.53
              36 42   1.43     37 43   2.04     38 44   1.12
              39 45   1.71     40 46    .91     41 47   1.32
              43  1   1.80     45  3   1.13     47  5    .23

 [NY,*,PH,*]   1  3    .04     12 14   4.68     13 15   5.61
              14 16   3.56     15 17   5.81     16 18   3.81
              17 19   6.31     18 20   4.07     19 21   7.33
              20 22   4.55     21 23   7.37     22 24   4.73
              23 25   7.61     24 26   4.92     25 27   7.91
              26 28   5.19     27 29   8.40     28 30   5.53
              29 31   9.32     30 32   5.51     31 33  10.33
              32 34   9.21     33 35  18.95     34 36  11.23
              35 37  16.85     36 38   7.29     37 39  10.89
              38 40   5.41     39 41   8.21     40 42   4.52
              41 43   6.99     42 44   3.92     43 45   6.21
              44 46   3.44     45 47   5.17     46 48   2.55
              47  1   1.24

 [PH,*,WA,*]   1  4    .20     14 17   4.49     15 18   3.53
              16 19   2.67     17 20   3.83     18 21   3.01
              19 22   4.12     20 23   3.15     21 24   4.67
              22 25   3.20     23 26   4.23     24 27   2.87
              25 28   3.84     26 29   2.60     27 30   3.80
              28 31   2.77     29 32   4.31     30 33   3.16
              31 34   4.88     32 35   3.45     33 36   5.55
              34 37   3.52     35 38   6.11     36 39   3.32
              37 40   5.53     38 41   3.03     39 42   4.51
              40 43   2.53     41 44   3.39     42 45   1.93
              43 46   2.52     44 47   1.20     45 48   1.75
              46  1    .88     47  2    .87     ;

end;