view release on metacpan or  search on metacpan

lib/Algorithm/Bertsekas.pm  view on Meta::CPAN

	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;
 }
 
 ### ---            final              --- ###
 ### --- simple and direct application --- ###

 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 ],