view release on metacpan or  search on metacpan

README  view on Meta::CPAN

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

 ### --- simple and direct application --- ###
 ### ---            start              --- ###

 #!/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]} ) {