Lindo Systems

! Unordered Lexico Maximization of Muli-Criteria. !          (MCknapULexMxMn.lng)
  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, Knapsack, Lexico-max, Minimax, Multi-criteria, Nucleolus,
     Pareto optimal, Pre-emptive goal programming, Unordered lexico-max;

SETS:
 CRITERIA: VAL_REC,
      base, sumjsmall, sofs;

 ITEM: WGT, Z; !Each item has a wgt, value, yes/no var;
 CXI( ITEM, CRITERIA) : VALUE;
 CxC( CRITERIA, CRITERIA): delta;
ENDSETS
DATA:
! Case 1;
!Case01; 
  ITEM       WGT  =
 ANT_REPEL    1     
 SIX_PACK     3    
 BLANKET      4    
 BRATWURST    3    
 BROWNIE      3   
 FRISBEE      1   
 SALAD        5   
 WATMELON    10 ;
! The value of the items to the various 'players',
 based on allocating 100 points to the items;
!Case01;  CRITERIA = TOM  DICK JANE;
!Case01;  VALUE =    3    9   12   ! ANT_REPEL;
!Case01;            14   20    2   ! SIX_PACK;
!Case01;             5   11   14   ! BLANKET;
!Case01;            13   21   11   ! BRATWURST;
!Case01;             6   12   11   ! BROWNIE; 
!Case01;            10   19   13   ! FRISBEE;
!Case01;             8    2   28   ! SALAD;
!Case01;            41    6    9;  ! WATMELON;
!Case01;   CAP =  15;

! Case 2;
!Case02 
  ITEM       WGT =
  ITEM1       15     
  ITEM2       14    
  ITEM3        7    
  ITEM4        8  ;
!Case02 
   CAP =  15;

!Case02  CRITERIA = DICK JANE;
!Case02  VALUE =     70    0 ! ITEM1;
!Case02               0   70 ! ITEM1;
!Case02              14   16 ! ITEM3;
!Case02              16   14;! ITEM1;

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( kn);
  ! Force delta( i, j) ! delta( i, j) = amount by which VAL_REC(i) falls short of base( 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 insert the regular constraints;
    @FOR( CRITERIA( k): ! Value of soln for criterion k;
      VAL_REC( k) = @SUM( ITEM( j): VALUE( j, k)* Z( j));
        );
       @SUM( ITEM(j): WGT(j)*Z(j)) <= CAP;! Wgt constraint;
       @FOR( ITEM(j): @BIN( Z(j)));       ! All vars 0/1;
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 messages; ! 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):
    kn = 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;

  @FOR( CRITERIA(c):
     @WRITE( @FORMAT( CRITERIA( c),'5s'));
      ); 
  @FOR( ITEM(j): @WRITE( @FORMAT( ITEM( j),'10s')));
  @WRITE( @NEWLINE(1));
 @FOR( CRITERIA( c):
     @WRITE( @FORMAT( VAL_REC( c),'5.0f'));
       );
   @FOR( ITEM(j):
     @IFC( Z( j) #GT# .5:   !Either;
        @WRITE('         1');
      @ELSE
        @WRITE('          ');
         );
   ); ! End FOR;


ENDCALC