Lindo Systems

! The invoice/payment matching problem.
You have sent a customer a number of invoices, say 100,
for 100 different services.  Your customer has sent you a number
of payments, say 20, without indicating which invoices
are covered by each payment. A payment typically covers several
invoices.  You want to match invoices
to payments, so as to identify which invoices are still not paid;
! Keywords: Accounting, Matching, Assignment, Finance, Subset sum, Invoicing;
sets:
   invoice: iamt;
   payment: pamt, errup, errdn;
   ixp( invoice, payment): z;
endsets
data:
! Invoice line item names,  amounts;
  invoice, iamt = 
   INV01 837.44  INV02 989.22  INV03 598.03 
   INV04 423.55  INV05  21.21  INV06  49.42
   INV07  23.40  INV08 962.10  INV09  43.10 
   INV10  11.01  INV11 587.91  INV12  53.24
   INV13 603.74 ;
! Payment names, amounts;
  payment, pamt = 
   PAY01 1012.62 PAY02  1021.58 PAY03 880.54
   PAY04  994.23 PAY05  1191.65;
enddata

submodel matchinv:
! Variables:
   z(i,p) = 1 is invoice i is assigned to payment p;

! Each invoice can be assigned to at most 1 payment;
 @for( invoice(i):
    @sum( ixp( i,p): z(i,p)) <= 1;
     );

! You either assign it or not;
 @for( ixp( i,p): @bin( z(i,p)));

! Compute error in matching payment p;
 @for( payment( p):
   errup( p) - errdn( p) = @sum( ixp( i, p): iamt(i)*z(i,p)) - pamt(p);
     );

! Minimize the relative error of matching each payment to 1 or more invoices;
  min = @sum( payment( p): (errup(p) + errdn(p))/ pamt( p));
! Minimize the absolute error;
!  min = @sum( payment( p): errup(p) + errdn(p));
endsubmodel

calc:
  @solve( matchinv);

  @write(' Matching payment amounts to invoice/line item amounts', @newline(1));
  @for( payment( p):
    paycum = 0;
    @for( ixp( i, p ) | z(i,p) #gt# 0.5:
      @write( @format( payment(p),'12s'),' ', @format( invoice(i),'12s'),' ',@format(iamt(i),'12.2f'),@newline(1));
      paycum = paycum + iamt(i);
        );
    @ifc( @abs( pamt(p) - paycum) #lt# 0.01:
       @write('  Total ', @format( pamt(p),'11.2f'),'  vs.   ',@format( paycum, '11.2f'), @newline(2));
      @else
       @write('  Total ', @format( pamt(p),'11.2f'),' *vs.*  ',@format( paycum, '11.2f'), @newline(2));
        );
      );
  paycum = 0;
  @for( invoice(i) | @sum( ixp(i,p): z(i,p)) #lt# 0.5:
    @write( '   Unassigned',@format( invoice(i),'12s'),' ', @format(iamt(i),'12.2f'), @newline(1));
     paycum = paycum + iamt(i);
      );
    @write('  Total                    ',@format( paycum, '11.2f'), @newline(1));

endcalc