! Stable Roommate Matching(stable_roommate8);
! Each of 2n people specify a rank, 1, 2,..., 2n-1, for
  each other person.  We want to pair up the people into
  a stable set of pairs, i.e., there are no two people 
  i and j who are not paired up, but would prefer to be
  paired up rather than be paired with their current partner.
  It may be that there is no such a stable pairing.  This 
  LINGO model will find such a pairing if one exists, and 
  will minimize the worst that any person gets treated under
  this pairing.
! Keywords: matching, assignment, room-mate matching,
  stable matching, pairing;
SETS:
 PERSON: AP;
 PXP(PERSON,PERSON): PREF, Y, R, NOSTAB;
ENDSETS
DATA:
! Example from Irving(1985);
  PERSON = 1..8;
 ! Row preference for col;
 PREF=!1  2  3  4  5  6  7  8;
      99  1  7  3  2  4  5  6
       3 99  1  7  6  2  4  5
       7  3 99  1  5  6  2  4
       1  7  3 99  4  5  6  2
       2  4  5  6 99  1  7  3
       6  2  4  5  3 99  1  7
       5  6  2  4  7  3 99  1
       4  5  6  2  1  6  3 99;
 ! E.g., the first choice of 1 is 2.  The first choice
   of 8 is 5.
 ! The 99 is to indicate that a person cannot be
   matched to himself.
 ! This data set has 3 stable matchings;
ENDDATA

! Y(i,j) = 1 if PERSON i and j are matched, for  i < j;
 
  NP = @SIZE(PERSON);
! Each person must be assigned;
  @FOR(PERSON(i):
    @SUM(PERSON(k)| k #GT# i: Y(i,k)) 
  + @SUM(PERSON(k)| k #LT# i: Y(k,i)) = 1;
      );

! Turn off the lower diagonal part of Y;
   @SUM( PXP(i,j)| i #GT# j: Y(i,j)) = 0;

! Enforce monogamy by making the Y(i,j) = 0 or 1;
   @FOR( PXP(i,j):
       @BIN(Y(i,j))
        );
    
! Stability conditions: Either person i and person j
   are assigned to each other, or
   person i gets a person k he prefers to j, or
   person j gets a person k he prefers to i, or
   there is no stable solution; 
  @FOR( PXP(i,j)| i #LT# j:
     Y(i,j)
   + @SUM( PERSON(k)| k #LT# i #AND# PREF(i,k) #LT# PREF(i,j): Y(k,i))
   + @SUM( PERSON(k)| k #GT# i #AND# PREF(i,k) #LT# PREF(i,j): Y(i,k))
   + @SUM( PERSON(k)| k #LT# j #AND# PREF(j,k) #LT# PREF(j,i): Y(k,j))
   + @SUM( PERSON(k)| k #GT# j #AND# PREF(j,k) #LT# PREF(j,i): Y(j,k))
   + NOSTAB(i,j) >= 1
        );

! Compute actual assigned rank for each person;
@FOR( PERSON(i):
  AP(i) = @SUM( PERSON(k)| i #LT# k: PREF(i,k)*Y(i,k))
        + @SUM( PERSON(k)| k #LT# i: PREF(i,k)*Y(k,i));
   PWORST >= AP(i);
    );

! Compute number of instabilities;
  NUMUSTAB = @SUM(PXP(i,j): NOSTAB(i,j));
! Apply most weight to getting a stable solution;
  MIN = NP*NP*NUMUSTAB + PWORST;