$TITLE  CREW SCHEDULING PROBLEM
$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 * L14 /
       J   routes   / R1 * R12 / ;

  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  /;


  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  ;

  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   ;