! Unordered Lexico maximization of allocations (inherit.lng)
 to several parties/participants.
  Given a number of participants(parties/criteria), each with their
own objective or utility function, we want to
find a solution to a shared problem so that the smallest
utility is maximized, given that, the second smallest
utility is maximized, given that, the third etc...
  It follows that the solution is Pareto optimal.
  The specific shared problem is to allocate a number
of discrete items from an inheritance to the heirs, with
each heir having her own set of values for each of the
items to be allocated;

! References:
Serafini, P. (1996), "Scheduling Jobs on Several Machines with the Job Splitting Property",
Operations Research, Vol. 44, No. 4, (July-August), pp. 617-628.
Maschler, M., B. Peleg, and L. S. Shapley (1979), 
"Geometric Properties of the Kernel, Nucleolus, and Related Solution Concepts",
 Mathematics of Operations Research, vol. 4, No. 4 (Nov), pp. 303-338.

!Keywords: Allocation, Assignment problem, Fair allocation, Goal programming,
     Inheritance, Lexico-max, Minimax, Nucleolus, Pareto optimal,
     Pre-emptive goal programming, Multi-criteria, Unordered lexico-max;
SETS:
  CRITERIA: VAL_REC,
      base, sumjsmall, sofs;
  CxC( CRITERIA, CRITERIA): delta;
  ITEM;
  IxC( ITEM, CRITERIA) : value, z;
ENDSETS
DATA:
  BigM = 9999; ! A number > any possible allocation;
! Data set 1, unique preferences;
  ITEM = Photos, Silver, Tables, Books_  HiFi__ Misc__;
! The parties receiving the allocations;
  CRITERIA =  Tom    Dick   Harry  Joan;
  value =
  !Photos;    21     14     23     10
  !Silver;    18     13     10     13
  !Tables;    26     10     20     31
  !Books;     12     39      5     23
  !HiFi;      15     17     40     14 
  !Misc;       8      7      2      9! Comments on this data set.  
  Notice that each person's valuations sum to 100. Thus, if all
 had identical valuations, the average that each would get would = 25.;

! Data set 2, common preferences, e.g., market value;
!  ITEM = Photos, Silver, Tables, Books_  HiFi__  Car___  Miscl_;
!  CRITERIA =  Tom    Dick   Harry  Joan;
!  value =
  !Photos    13     13     13     13
  !Silver    21     21     21     21
  !Tables    18     18     18     18
  !Books_    15     15     15     15
  !HiFi__    10     10     10     10 
  !Car___    15     15     15     15
  !Misc__     8      8      8      8 ;
ENDDATA

SUBMODEL ULexMxMn:
! Maximize the sum of the k smallest VAL_REC(i)
  Variables:
    VAL_REC(j) = the utility (more is better) achieved by CRITERIA j,
    base( j) = jth smallest VAL_REC(i) when maximizing the
              sum of the j smallest VAL_REC(i),
    delta( i, j) = amount by which VAL_REC(i)
                 is less than base( j), when maximizing the
                 sum of j smallest, = 0 if >= base(j)
    sofs( k) = sum of k smallest values received;
  MAX = sofs( k);
  ! Force delta( i, j)   @FOR( CRITERIA( i):
     @FOR( CRITERIA( j) : 
    [NFORC] delta( i, j) >= base( j) - VAL_REC( i)  ;
         );
       );
  ! Notice or verify that in the constraints,
      sofs( k) =  k* base( k) - @sum( CRITERIA( i): delta( i, k)), and
     delta( i, j) >= base( j) - VAL_REC( i)  
  We can maximize sofs( k) if we
  set base( k)  = kth smallest of the VAL_REC( i), then
  sofs( k) = sum of the k smallest.  Notice that
  for any other value of base( k), sofs( k) <= sum of k smallest; 
 
  @FOR( CRITERIA( j):
    @free( base( j));  ! Allow < 0;
    @FREE( sofs( j));
   [LVL]  sofs( j) =  j* base( j) - @SUM( CRITERIA( i): delta( i, j));
! Limit sum of j smallest for j < k;
   [PREVP] sofs( j) >= sumjsmall( j);
      );

! Here are the regular constraints;
! Constraints on permissible allocations;
!  Can assign object i to at most one CRITERIA;
  @FOR( ITEM( i):
      @SUM( CRITERIA(j): z( i, j)) <= 1;
      );
  @FOR( IxC( i, j): @BIN( z( i, j)));

! VAL_REC(j) = utility of CRITERIA j;
  @FOR( CRITERIA( j):
     VAL_REC( j) = @SUM( ITEM( i): value( i, j)* z( i, j));
      );
ENDSUBMODEL


CALC:
 !Algorithm:
   For k = 1, 2, ... @SIZE( CRITERIA):
    {Minimize sumjsmall( k) = the sum of k smallest values received,
    Constrain sum of k smallest to >= sumjsmall(k),
    }
  Result:
    The smallest is maximized,
    Given the smallest 1 maximized, the 2nd smallestest is maximized,
    Given the smallest 2 maximized, etc.
   ;
 @SET("TERSEO",2);  !Turn off default output;
 ! Successively maximize the sum of the k smallest,
   for k = 1, 2, N;
 N = @SIZE( CRITERIA);
 !Initialize;
  @FOR( CRITERIA( i):
     sumjsmall( i) = - BigM;
      );

 PREV = 0;
 @FOR( CRITERIA( kk):
    k= kk;
!   @gen( ULexMxMn);
   @SOLVE( ULexMxMn);
   @WRITE(' Max sum of smallest ', kk,' = ', @FORMAT( sofs( kk),'2.0f'),@NEWLINE(1));
   @WRITE( '  ',kk,'th smallest is ',@FORMAT( sofs( kk)-PREV,'2.0f'), @NEWLINE(1));
   PREV = sofs( kk);
   sumjsmall( kk) = sofs( kk);
     );

 ! Display the solution;
 @WRITE(@NEWLINE(1),'   Allocation:  ', @NEWLINE(1),'       ');
 @FOR( CRITERIA(j): @WRITE(' ',CRITERIA(j)));
 @WRITE( @NEWLINE(1));
 @FOR( ITEM(t):
   @WRITE(' ',ITEM(t));
   @FOR(CRITERIA(j):
     @WRITE( '   ',@FORMAT( z( t, j),'1.0f'),' ');
       );
   @WRITE( @NEWLINE(1));
     );
 @WRITE(' Total');
 @FOR( CRITERIA( j):
   @WRITE('  ',@FORMAT(VAL_REC(j),'3.0f'));
     );
 @WRITE(@NEWLINE(1));
ENDCALC