! Stable Marriage Assignment (stable_marriage.lng);
!  Each of n men (job applicants?) specify a rank, 1, 2,..., n, for
  each of n women (potential employers?). 
   Similarly, each of the n women specify a rank for 
  each of the men.
  We want to assign or match the men and women in
  couples that are stable, i.e., there will be no man 
  i and woman j who are not paired up, but would 
  prefer to be paired up rather than be paired 
  with their current partner. (Tempted to have an affair?) 
  This LINGO model will find such a pairing that will 
  minimize the worst that any person gets treated under
  this pairing. This problem is a variant of the
  National Resident Matching Program in U.S. medicine (NRMP).
! Ref. Gale and Shapley;
! Other applications are in highschool or college admissions,
  or the Human Resources (HR) task of 
  matching applicants to jobs in a large organization;
! Keywords: Assignment, College admissions, Highschool admissions, 
     HR, Marriage, Matching, NRMP, Pairing, Recruiting, 
     Rostering, Stable matching;

SETS:
 MAN: AM;
 WOMAN: AW;
 MXW( MAN, WOMAN): MPREF, WPREF, Z, RM, RW;
ENDSETS
DATA:
 ! One can always make the number of MAN = number of WOMAN
   by adding extra entries to the one that is short
   with a ranking number that is high (not preferred);
   MAN = ADAM  BOB  CHUCK  DON;
 WOMAN= ALICE BARB CARMEN DOLLY;
 ! Men(row) preference for women(col),
   lower is more preferred;
 MPREF =
          1     2     3     4 !ADAM;
          1     4     3     2 !BOB;
          3     1     2     4 !CHUCK;
          2     3     1     4;!DON;
 ! Women(col) preference for men(row)
   lower is more preferred;
 WPREF =
          4     2     1     4 !ADAM;
          3     3     2     3 !BOB;
          1     4     3     2 !CHUCK;
          2     1     4     1;!DON;
! Thus, Adam's first choice is Alice.
     Alice's first choice is Chuck;
! There are 2 stable solutions to this data set,
 one where the men do relatively well, the
 other where the women do relatively well;
ENDDATA

SUBMODEL STABLE:
! Z(i,j) = 1 if man i is assigned to woman j;
 
! Each man must be assigned;
  @FOR( MAN(i):
    @SUM( WOMAN(j): Z(i,j)) = 1;
      );
! Each woman must be assigned;
  @FOR( WOMAN(j):
    @SUM( MAN(i): Z(i,j)) = 1;
      );

! Enforce monogamy by making the Z(i,j) = 0 or 1;
   @FOR( MXW(i,j):
       @BIN( Z(i,j))
        );

! Stability conditions: 
   If man i and woman j are not matched ( Z(i,j) = 0), it means
  either man i got a woman k he  prefers to j, 
    or woman j got a   man k she prefers to i; 
  @FOR( MXW(i,j):
     Z(i,j)
   + @SUM( WOMAN(k)| MPREF(i,k) #LT# MPREF(i,j): Z(i,k))
   + @SUM( MAN(k)| WPREF(k,j) #LT# WPREF(i,j): Z(k,j)) >= 1
        );

! Compute actual assigned rank for each man and woman;
@FOR( MAN(i):
  AM(i) = @SUM( WOMAN(k): MPREF(i,k)* Z(i,k));
  PWORSTM >= AM(i); ! Worst match for men;
    );
@FOR( WOMAN(j):
  AW(j) = @SUM(   MAN(k): WPREF(k,j)* Z(k,j));
  PWORSTW >= AW(j); ! Worst match for women;
   );
 
! There are various objectives one might use to choose
 among alternative stable solutions, ex.; 
! Total not best;
  PWORSTT = @SUM( MXW( i, j): ( MPREF( i, j) + WPREF( i, j))* Z( i, j));
! Minimize the worst given to anyone;
  PWORST >= PWORSTM;
  PWORST >= PWORSTW;

! Minimize worst by anyone;
!  MIN = PWORST;
! Minimize worst by MAN;
!  MIN = PWORSTM;
! Minimize worst by WOMAN;
!  MIN = PWORSTW;
! Minimize worst in total;
  MIN = PWORSTT;
ENDSUBMODEL


CALC:
 @SOLVE( STABLE);
 @WRITE( ' The matches are:', @NEWLINE( 1));
 @WRITE( '   Man      Woman  ManPref  WomPref', @NEWLINE(1));
 @FOR( MXW(i,j) | Z(i,j) #GT# 0.5:
  @WRITE(@FORMAT( MAN(i),'6s'),' <=> ',@FORMAT( WOMAN(j),'6s'),'  ',
    @FORMAT( MPREF(i,j),'4.0f'),'    ',@FORMAT( WPREF(i,j),'4.0f'),@NEWLINE(1));
    );
 ! Make sure the worsts are not overstated if not explicitly minimized;
 PWORSTM = @MAX(   MAN( k): AM( k));
 PWORSTW = @MAX( WOMAN( k): AW( k));
 PWORST = @SMAX( PWORSTM, PWORSTW);
 @WRITE( @NEWLINE( 1));
 @WRITE( PWORSTM,' = Worst for man', @NEWLINE( 1));
 @WRITE( PWORSTW,' = Worst for woman', @NEWLINE( 1));
 @WRITE( PWORSTT,' = Worst in total', @NEWLINE( 1));
ENDCALC