Algorithm-Bertsekas
view release on metacpan or search on metacpan
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
### --- simple and direct application --- ###
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
# There is at least one object in the @objects_with_greater_benefits list whose price is updated ? use old list : generate new list;
for my $object ( @objects_with_greater_benefits ) # use old list
{
my $matrix_value = $seen_ghost ? 0 : $matrix[$person]->[$object];
$current_value{$object} = $matrix_value - $price_object{$object};
push @updated_price, $object if ( $objects_desired_by_this{$person}{$object} == $current_value{$object} );
if ( $current_value{$object} > $Opt01ValForPersonI ) # search for the best 3 objects
{
$Opt03ValForPersonI = $Opt02ValForPersonI;
$Opt03ObjForPersonI = $Opt02ObjForPersonI;
$Opt02ValForPersonI = $Opt01ValForPersonI;
$Opt02ObjForPersonI = $Opt01ObjForPersonI;
$Opt01ValForPersonI = $current_value{$object};
$Opt01ObjForPersonI = $object;
$Opt01ValForPersonI_old_list = $Opt01ValForPersonI;
}
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
if ( not @updated_price and not $locked_list{$person} ) # if all prices are outdated
{
for my $object ( 0 .. $max_size - 1 ) # generate new list
{
next if ( defined $current_value{$object} );
my $matrix_value = $seen_ghost ? 0 : $matrix[$person]->[$object];
$current_value{$object} = $matrix_value - $price_object{$object};
if ( $current_value{$object} > $Opt01ValForPersonI_new_list ) # to find the best 3 objects in the complementary subset <new list>
{
$Opt03ValForPersonI_new_list = $Opt02ValForPersonI_new_list;
$Opt03ObjForPersonI_new_list = $Opt02ObjForPersonI_new_list;
$Opt02ValForPersonI_new_list = $Opt01ValForPersonI_new_list;
$Opt02ObjForPersonI_new_list = $Opt01ObjForPersonI_new_list;
$Opt01ValForPersonI_new_list = $current_value{$object};
$Opt01ObjForPersonI_new_list = $object;
}
elsif ( $current_value{$object} > $Opt02ValForPersonI_new_list )
{
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
if ( $verbose >= 8 ){
printf $output " personI = %3s ; objectJ = %3s ; Current Value %20.5f = \$matrix[%3s][%3s] %12.0f - \$price_object{%3s} %20.5f <new list> Max01_CurVal = %12.5f (%3s), Max02_CurVal = %12.5f (%3s), Max03_CurVal = %12.5f (%3s)\n",
$person, $object, $current_value{$object}, $person, $object, $matrix_value, $object, $price_object{$object},
$Opt01ValForPersonI_new_list, defined $Opt01ObjForPersonI_new_list ? $Opt01ObjForPersonI_new_list : '',
$Opt02ValForPersonI_new_list, defined $Opt02ObjForPersonI_new_list ? $Opt02ObjForPersonI_new_list : '',
$Opt03ValForPersonI_new_list, defined $Opt03ObjForPersonI_new_list ? $Opt03ObjForPersonI_new_list : '';
}
}
# to find the best 3 out of 6 objects
if ( $Opt01ValForPersonI_new_list > $Opt01ValForPersonI )
{
$Opt03ValForPersonI = $Opt02ValForPersonI;
$Opt03ObjForPersonI = $Opt02ObjForPersonI;
$Opt02ValForPersonI = $Opt01ValForPersonI;
$Opt02ObjForPersonI = $Opt01ObjForPersonI;
$Opt01ValForPersonI = $Opt01ValForPersonI_new_list;
$Opt01ObjForPersonI = $Opt01ObjForPersonI_new_list;
}
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
$locked_list{$person} = 1 if ( $epsilon_scaling > (1/10) * $max_epsilon_scaling and ($Opt03ValForPersonI - $Opt01ValForPersonI_new_list) > $min_size * $epsilon );
$locked_list{$person} = 1 if ( $epsilon_scaling > (3/10) * $max_epsilon_scaling ); # Lock the old list. Is this the minimum value to find a possible solution?
delete $locked_list{$person} if ( $epsilon == 1/(1+$min_size) ); # Otherwise unlock the person's old list in the last $epsilon_scaling round.
}
if ( $verbose >= 8 ){
my @old_list = sort { $a <=> $b } @objects_with_greater_benefits;
my @new_list = sort { $a <=> $b } keys %{$objects_desired_by_this{$person}};
@updated_price = sort { $a <=> $b } @updated_price;
my @best_3_objects = ( $Opt01ObjForPersonI, $Opt02ObjForPersonI, $Opt03ObjForPersonI );
my $msg = $locked_list{$person} ? '[locked list] ' : '';
@objects_with_same_values = sort { $a <=> $b } @objects_with_same_values;
$this_person_can_choose_n_different_objects{$person}{'objects'} = \@objects_with_same_values; #reference to an array
printf $output "<> PersonI = %3s ; %3s objects desired by this person (old list) = (@old_list) ; objects whose current values are still updated = (@updated_price) : %2s >= 1 ? \n", $person, scalar @old_list, scalar @updated_price;
printf $output "<> PersonI = %3s ; %3s objects desired by this person (new list) = (@new_list) $msg; \@best_3_objects = (@best_3_objects) \n", $person, scalar @new_list if ( defined $Opt03ObjForPersonI );
printf $output "<> PersonI = %3s chose ObjectJ = %3s ; \$bidForPersonI %10.5f = \$Opt01ValForPersonI %.5f - \$Opt02ValForPersonI %.5f + \$epsilon %.5f \n", $person, $Opt01ObjForPersonI, $bidForPersonI, $Opt01ValForPersonI, $Opt02ValForPersonI, $e...
printf $output "<> PersonI = %3s ; these objects (@objects_with_same_values) have the same values \$Opt01ValForPersonI = %10.5f ; \$Opt01ObjForPersonI = $Opt01ObjForPersonI ; *** equal values *** \n", $person, $Opt01ValForPersonI if (@objects_wit...
}
}
}
# first, choose objects that appear a few times
foreach my $object ( sort { $count_object{$a} <=> $count_object{$b} || $seen_assignned_objects{$a} <=> $seen_assignned_objects{$b} } keys %objects_with_the_same_values ){ # sort { $price_object{$b} <=> $price_object{$a} }
foreach my $person ( keys %{$objects_with_the_same_values{$object}} ){ # sort { $objects_with_the_same_values{$object}{$a} <=> $objects_with_the_same_values{$object}{$b} }
lib/Algorithm/Bertsekas.pm view on Meta::CPAN
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
=head1 SYNOPSIS
### --- simple and direct application --- ###
( run in 0.471 second using v1.01-cache-2.11-cpan-4e96b696675 )