NAME

       Algorithm::Bertsekas - auction algorithm for the assignment problem.

       This is a perl implementation for the auction algorithm for the asymmetric (N<=M) assignment problem.

DESCRIPTION

The assignment problem in the general form can be stated as follows:

"Given N jobs (or persons), M tasks (or objects) and the effectiveness of each job for each task,
the problem is to assign each job to one and only one task in such a way that the measure of
effectiveness is optimised (Maximised or Minimised)."

"Each assignment problem has associated with a table or matrix. Generally, the rows contain the
jobs (or persons) we wish to assign, and the columns comprise the tasks (or objects) we want them
assigned to. The numbers in the table are the costs associated with each particular assignment."

In Auction Algorithm (AA) the N persons iteratively submit the bids to M objects.
The AA take cost Matrix N�M = [aij] as an input and produce assignment as an output.
In the AA persons iteratively submit the bids to the objects which are then reassigned
to the bidders which offer them the best bid.

Another application is to find the (nearest/more distant) neighbors.
The distance between neighbors can be represented by a matrix or a weight function, for example:
1: f(i,j) = abs ($array1[i] - $array2[j])
2: f(i,j) = ($array1[i] - $array2[j]) ** 2


SYNOPSIS

#!/usr/bin/perl

use strict;
use warnings FATAL => 'all';
use diagnostics;
use Algorithm::Bertsekas qw(auction); # To install this modulus: 'cpan Algorithm::Bertsekas' or 'ppm install Algorithm-Bertsekas'

my @array1; my @array2;
my @input_matrix;

my $N = 10;
my $M = 10;
my $range = 1000;

for my $i (1..$N) {
       push @array1, sprintf( "%.0f", rand($range) );
}

for my $i (1..$M) {
       push @array2, sprintf( "%.0f", rand($range) );
}

print "\n \@array1 = ( ";
for my $value (@array1) { printf("%4.0f ", $value); }
print ")\n";

print " \@array2 = ( ";
for my $value (@array2) { printf("%4.0f ", $value); }
print ")\n";

for my $i ( 0 .. $#array1 ){
       my @weight_function;
       for my $j ( 0 .. $#array2 ){
               #my $weight = sprintf( "%.0f", rand($range) );
               my $weight = abs ($array1[$i] - $array2[$j]);
               push @weight_function, $weight;
       }
       push @input_matrix, \@weight_function;
}

print "\n The Nearest Neighbors and the Matrix of the weight function f(i,j) between each element of the two vectors \@array1 and \@array2.";
print "\n The weight function chosen can be the modulus of the difference between two real numbers: f(i,j) = abs (\$array1[i] - \$array2[j]). \n\n \@input_matrix = \n\n ";
print " " x 7;
printf("%4.0f ", $_ ) for @array2;
print "\n\n";
for my $i ( 0 .. $#input_matrix ) {
       printf(" %4.0f [ ", $array1[$i] );
       for my $j ( 0 .. $#{$input_matrix[$i]} ) {
               printf("%4.0f ", $input_matrix[$i]->[$j] );
       }
       print "]\n";
}

my ( $optimal, $assignment_ref, $output_index_ref ) = auction( matrix_ref => \@input_matrix, maximize_total_benefit => 0, verbose => 10 );

print "\n";

my $sum = 0;
for my $i ( 0 .. $#{$output_index_ref} ){
       my $j = $output_index_ref->[$i];
       my $value = $input_matrix[$i]->[$j];
       $sum += $value if (defined $value);

       $value = defined $value ? sprintf( "%6s", $value ) : ' ' x 6 ; # %6s
       printf " Auction Algorithm, (row, column) indexes --> \$i = %3d ; \$j = %3d ; \$value = $value ; \$sum = %8s \n", $i, $j, $sum;
}

Example 1: Find the nearest neighbor, Minimize the total benefit.

my @array1 = ( 893, 401, 902, 576, 767, 917, 76, 464, 124, 207, 125, 530 );
my @array2 = ( 161, 559, 247, 478, 456 );

my @input_matrix;
for my $i ( 0 .. $#array1 ){
  my @weight_function;
  for my $j ( 0 .. $#array2 ){
     my $weight = abs ($array1[$i] - $array2[$j]);
     #  $weight =     ($array1[$i] - $array2[$j]) ** 2;  # another option
     push @weight_function, $weight;
  }
  push @input_matrix, \@weight_function;
}

      161 559 247 478 456

893 [ 732 334 646 415 437 ]
401 [ 240 158 154  77  55 ]
902 [ 741 343 655 424 446 ]
576 [ 415  17 329  98 120 ]
767 [ 606 208 520 289 311 ]
917 [ 756 358 670 439 461 ]
 76 [  85 483 171 402 380 ]
464 [ 303  95 217  14   8 ]
124 [  37 435 123 354 332 ]
207 [  46 352  40 271 249 ]
125 [  36 434 122 353 331 ]
530 [ 369  29 283  52  74 ]

my ( $optimal, $assignment_ref, $output_index_ref ) = auction( matrix_ref => \@input_matrix, maximize_total_benefit => 0, verbose => 5 );

Objective: to Minimize the total benefit
Number of left nodes: 12
Number of right nodes: 5
Number of edges: 60

Solution:
Optimal assignment: sum of values = 153
Feasible assignment condition: stepsize = 0.1667 < 1/5 = 0.2
Number of iterations: 50

row index    = [  0   1   2   3   4   5   6   7   8   9  10  11 ]
column index = [  9   8  10   1   5  11   7   4   6   2   0   3 ]
matrix value = [             17               8      40  36  52 ]

modified matrix 5 x 9:
[ 516   341   150   671   453   719   710   720** 387  ]
[ 598   739** 548   273   661   321   404   322   727  ]
[ 602   427   236   585   539   633   716** 634   473  ]
[ 679   658   467   354   742   402   485   403   704**]
[ 701   636   445   376   748** 424   507   425   682  ]

original matrix 12 x 5 with solution:
[ 732   334   646   415   437  ]
[ 240   158   154    77    55  ]
[ 741   343   655   424   446  ]
[ 415    17** 329    98   120  ]
[ 606   208   520   289   311  ]
[ 756   358   670   439   461  ]
[  85   483   171   402   380  ]
[ 303    95   217    14     8**]
[  37   435   123   354   332  ]
[  46   352    40** 271   249  ]
[  36** 434   122   353   331  ]
[ 369    29   283    52**  74  ]

Pairs (in ascending order of matrix values):
  indexes (  7,  4 ), matrix value =   8 ; sum of values =     8
  indexes (  3,  1 ), matrix value =  17 ; sum of values =    25
  indexes ( 10,  0 ), matrix value =  36 ; sum of values =    61
  indexes (  9,  2 ), matrix value =  40 ; sum of values =   101
  indexes ( 11,  3 ), matrix value =  52 ; sum of values =   153
  indexes (  0,  9 ), matrix value =     ; sum of values =   153
  indexes (  1,  8 ), matrix value =     ; sum of values =   153
  indexes (  2, 10 ), matrix value =     ; sum of values =   153
  indexes (  4,  5 ), matrix value =     ; sum of values =   153
  indexes (  5, 11 ), matrix value =     ; sum of values =   153
  indexes (  6,  7 ), matrix value =     ; sum of values =   153
  indexes (  8,  6 ), matrix value =     ; sum of values =   153

Example 2: Maximize the total benefit.

my $N = 10;
my $M = 10;
my $r = 100;

my @input_matrix;
for my $i ( 0 .. $N - 1 ){
  my @weight_function;
  for my $j ( 0 .. $M - 1 ){
     my $weight = sprintf( "%.0f", rand($r) );
     push @weight_function, $weight;
  }
  push @input_matrix, \@weight_function;
}

Alternatively, we can define the matrix with its elements:

my @input_matrix = (
[  84,  94,  75,  56,  66,  95,  39,  53,  73,   4 ],
[  76,  71,  56,  49,  29,   1,  40,  40,  72,  72 ],
[  85, 100,  71,  23,  47,  18,  82,  70,  30,  71 ],
[   2,  95,  71,  89,  73,  73,  48,  52,  90,  51 ],
[  65,  28,  77,  73,  24,  28,  75,  48,   8,  81 ],
[  25,  27,  35,  89,  98,  10,  99,   3,  27,   4 ],
[  58,  15,  99,  37,  92,  55,  52,  82,  73,  96 ],
[  11,  75,   2,   1,  88,  43,   8,  28,  98,  20 ],
[  52,  95,  10,  38,  41,  64,  20,  75,   1,  47 ],
[  50,  80,  31,  90,  10,  83,  51,  55,  57,  40 ]
);

my ( $optimal, $assignment_ref, $output_index_ref ) = auction( matrix_ref => \@input_matrix, maximize_total_benefit => 1, verbose => 3 );

Objective: to Maximize the total benefit
Number of left nodes: 10
Number of right nodes: 10
Number of edges: 100

Solution:
Optimal assignment: sum of values = 893
Feasible assignment condition: stepsize = 0.09091 < 1/10 = 0.1
Number of iterations: 27

row index    = [  0   1   2   3   4   5   6   7   8   9 ]
column index = [  5   0   1   8   9   6   2   4   7   3 ]
matrix value = [ 95  76 100  90  81  99  99  88  75  90 ]

original matrix 10 x 10 with solution:
[  84    94    75    56    66    95**  39    53    73     4  ]
[  76**  71    56    49    29     1    40    40    72    72  ]
[  85   100**  71    23    47    18    82    70    30    71  ]
[   2    95    71    89    73    73    48    52    90**  51  ]
[  65    28    77    73    24    28    75    48     8    81**]
[  25    27    35    89    98    10    99**   3    27     4  ]
[  58    15    99**  37    92    55    52    82    73    96  ]
[  11    75     2     1    88**  43     8    28    98    20  ]
[  52    95    10    38    41    64    20    75**   1    47  ]
[  50    80    31    90**  10    83    51    55    57    40  ]

Pairs (in ascending order of matrix values):
  indexes (  8,  7 ), matrix value =  75 ; sum of values =  75
  indexes (  1,  0 ), matrix value =  76 ; sum of values = 151
  indexes (  4,  9 ), matrix value =  81 ; sum of values = 232
  indexes (  7,  4 ), matrix value =  88 ; sum of values = 320
  indexes (  3,  8 ), matrix value =  90 ; sum of values = 410
  indexes (  9,  3 ), matrix value =  90 ; sum of values = 500
  indexes (  0,  5 ), matrix value =  95 ; sum of values = 595
  indexes (  5,  6 ), matrix value =  99 ; sum of values = 694
  indexes (  6,  2 ), matrix value =  99 ; sum of values = 793
  indexes (  2,  1 ), matrix value = 100 ; sum of values = 893

OPTIONS

matrix_ref => \@input_matrix,   reference to array: matrix N x M.
maximize_total_benefit => 0,    0: minimize the total benefit ; 1: maximize the total benefit.
inicial_stepsize       => 1,    auction algorithm terminates with a feasible assignment if the problem data are integer and stepsize < 1/min(N,M).
inicial_price          => 0,
verbose                => 3,    print messages on the screen, level of verbosity, 0: quiet; 1, 2, 3, 4, 5, 8, 9, 10: debug information.

EXPORT

   "auction" function by default.

INPUT

   The input matrix should be in a two dimensional array (array of array)
       and the 'auction' subroutine expects a reference to this array.

OUTPUT

   The $output_index_ref is the reference to the output_index array.
       The $assignment_ref  is the reference to the assignment hash.
       The $optimal is the total benefit which can be a minimum or maximum value.


SEE ALSO

       1. Network Optimization: Continuous and Discrete Models (1998).
          Dimitri P. Bertsekas
          http://web.mit.edu/dimitrib/www/netbook_Full_Book.pdf

       2. Towards auction algorithms for large dense assignment problems (2008).
          Libor Bus and Pavel Tvrdik
          https://pdfs.semanticscholar.org/b759/b8fb205df73c810b483b5be2b1ded62309b4.pdf

       3. https://github.com/EvanOman/AuctionAlgorithmCPP/blob/master/auction.cpp
          This Perl algorithm started from this C++ implementation.

       4. https://en.wikipedia.org/wiki/Assignment_problem

       5. https://en.wikipedia.org/wiki/Auction_algorithm


AUTHOR

   Claudio Fernandes de Souza Rodrigues
       May 19, 2018
       Sao Paulo, Brasil
       [email protected]

COPYRIGHT AND LICENSE

Copyright (c) 2018 Claudio Fernandes de Souza Rodrigues.  All rights reserved.

This program is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.