$TITLE  CREW SCHEDULING PROBLEM - LARGE
$OFFUPPER
* This problem minimizes costs of crew scheduling
*   subject to covering the legs of the routes
*
*  References: 
*              The model is taken from pg 371 in Magnanti et al text.
*

  SETS
       I   legs of routes / L1 * L54 /
       J   routes   / R1 * R20 / ;

  PARAMETERS

  C(J)  fixed costs for routes
   /R1   130
    R2   130
    R3   130
    R4   90
    R5   80
    R6   200
    R7   90 
    R8   190
    R9   190
    R10  115
    R11  100
    R12  85 
    R13  130
    R14  201
    R15   19
    R16   80
    R17   24
    R18   29
    R19   64
    R20   25 /;
*    R21   26
*    R22   52
*    R23   94
*    R24  120
*    R25  130
*    R26  140
*    R27   70
*    R28  130
*    R29  110
*    R30  100
*    R31   90
*    R32  100
*    R33  210
*    R34  100 /;


  TABLE  A(I,J)  0 or 1 indicating if leg i is covered by route j
     R1    R2    R3    R4    R5    R6    R7  R8  R9  R10  R11  R12
L1   1     0     0      0     0     0     0       1
L2   0     0     0      0     1     1     0   1
L3   1     0     0      0     0     0     0            1
L4   0     0     0      0     0     0     1                     1 
L5   0     0     0      0     0     1     0   1
L6   0     1     1      0     0     0     0       1        1
L7   0     0     0      1     0     0     0       1
L8   0     1     1      0     0     1     0   1            1 
L9   0     1     1      0     0     1     0   1   1        1
L10  0     1     1      0     0     1     0   1   1        1
L11  1     0     0      0     1     0     0            1
L12  0     0     0      1     0     0     0       1
L13  0     0     0      1     0     0     0    
L14  1     0     0      0     0     0     1            1         1  
L15  1           1                            1
L16        1     1                                     1         1
L17                           1           1                 1
L18                     1           1                  1
L19              1                  1             1
L20              1            1           1   1
L21        1            1           1             1         1    1
L22        1            1     1                        1
L23  1           1
L24        1            1                     1             1           ;

  VARIABLES
       X(J) 0 or 1 indicating if crew j is assigned
       Z       total costs ;

  BINARY VARIABLE X ;

  EQUATIONS
       COST        define objective function
       PART(I)  set partitioning or covering for each leg ;

  COST ..        Z  =E=  SUM( J, C(J)*X(J) ) ;

PART(I) ..   SUM(J, A(I,J)*X(J) ) =G= 1 ;


  MODEL  CREWSCHD /ALL/ ;

  SOLVE CREWSCHD USING MIP MINIMIZING Z ;

  DISPLAY X.L, X.M   ;