Algorithm-Bertsekas
view release on metacpan or search on metacpan
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 ]
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 ]
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT = qw( auction );
our $VERSION = '0.87';
#Variables global to the package
my $maximize_total_benefit;
my $matrix_spaces; # used to print messages on the screen
my $decimals; # the number of digits after the decimal point
my ( $array1_size, $array2_size, $min_size, $max_size, $original_max_size );
my ( $need_transpose, $inicial_price, $iter_count_global, $iter_count_local );
my ( $epsilon_scaling, $max_epsilon_scaling, $max_matrix_value, $target, $output );
my ( %index_correlation, %assignned_object, %assignned_person, %price_object );
my ( %objects_desired_by_this, %locked_list, %seen_person, %seen_assignned_objects );
sub auction { # => default values
my %args = ( matrix_ref => undef, # reference to array: matrix N x M
maximize_total_benefit => 0, # 0: minimize_total_benefit ; 1: maximize_total_benefit
inicial_stepsize => undef, # auction algorithm terminates with a feasible assignment if the problem data are integer and stepsize < 1/min(N,M)
inicial_price => 0,
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
%locked_list = ();
%seen_person = ();
my @matrix_input = @{$args{matrix_ref}}; # Input: Reference to the input matrix (NxM) = $min_size x $max_size
$array1_size = $#matrix_input + 1;
$array2_size = $#{$matrix_input[0]} + 1;
$min_size = $array1_size < $array2_size ? $array1_size : $array2_size ; # square matrix --> $min_size = $max_size and $array1_size = $array2_size
$max_size = $array1_size < $array2_size ? $array2_size : $array1_size ;
$original_max_size = $max_size;
$target = 'auction-' . $array1_size . 'x' . $array2_size . '-output.txt' ;
if ( $args{verbose} >= 8 ){
print "\n verbose = $args{verbose} ---> print the verbose messages to <$target> file \n";
if ( open ( $output, '>', $target ) ) {
print "\n *** Open <$target> for writing. *** \n";
} else {
$args{verbose} = 7;
warn "\n *** Could not open <$target> for writing: $! *** \n";
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
$output_index[$index_i] = $index_j;
$seeN{$index_i}++;
$seeM{$index_j}++;
#print " \$output_index[$index_i] = $index_j \n";
next unless ( defined $matrix_input[$index_i] and defined $matrix_input[$index_i]->[$index_j] );
$assignment_hash{ $index_i } = $index_j;
$optimal_benefit += $matrix_input[$index_i]->[$index_j];
}
for my $i ( 0 .. $original_max_size - 1 ) {
for my $j ( 0 .. $original_max_size - 1 ) {
next if ($seeN{$i} or $seeM{$j});
$output_index[$i] = $j;
$seeN{$i}++;
$seeM{$j}++;
last;
}}
if ( $args{verbose} >= 8 ){
printf $output "\n\$optimal_benefit = $optimal_benefit ; \$iter_count_global = $iter_count_global ; \$epsilon = %.4g ; \@output_index = (@output_index) \n", $epsilon;
}
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
my $weight;
$weight = ( defined $matrix_input[$i] and defined $matrix_input[$i]->[$j] ) ? sprintf( "%${matrix_spaces}.${decimals}f ", $matrix_input[$i]->[$j] ) : ' ' x ($matrix_spaces+1) ;
print $weight;
}
print "]\n\n";
}
if ( $verbose >= 2 ){
my $index_length = length($original_max_size);
if ( $verbose >= 3 ){
printf " modified matrix %d x %d:\n", $#matrix + 1, $#{$matrix[0]} + 1;
for my $i ( 0 .. $#matrix ) {
print " [";
for my $j ( 0 .. $#{$matrix[$i]} ) {
printf(" %${matrix_spaces}.${decimals}f", $matrix[$i]->[$j] );
if ( $j == $matrix_index[$i] ){ print "**"; } else{ print " "; }
}
print "]\n";
}
print "\n";
}
print " original matrix $array1_size x $array2_size with solution:\n";
for my $i ( 0 .. $#matrix_input ) {
print " [";
for my $j ( 0 .. $#{$matrix_input[$i]} ) {
printf(" %${matrix_spaces}.${decimals}f", $matrix_input[$i]->[$j] );
if ( $j == $output_index[$i] ){ print "**"; } else{ print " "; }
}
print "]\n";
}
my %orderly_solution;
for my $i ( 0 .. $original_max_size - 1 ){
my $j = $output_index[$i];
my $weight = $max_matrix_value;
$weight = $matrix_input[$i]->[$j] if ( defined $matrix_input[$i] and defined $matrix_input[$i]->[$j] ); # condition for valid solution
$orderly_solution{ $weight } { $i } { 'index_array1' } = $i;
$orderly_solution{ $weight } { $i } { 'index_array2' } = $j;
}
print "\n Pairs (in ascending order of matrix values):\n";
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
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 ]
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
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 ]
( run in 0.224 second using v1.01-cache-2.11-cpan-069f9db706d )