Algorithm-Bertsekas

 view release on metacpan or  search on metacpan

README  view on Meta::CPAN

 
 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;

README  view on Meta::CPAN

  
	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 21, 2018

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

	
	#$max_epsilon_scaling = 20;
	#my $factor = exp ( (log( $epsilon * (1+$min_size) )) / ($max_epsilon_scaling-1) ); print "\n \$max_epsilon_scaling = $max_epsilon_scaling ; \$factor = $factor \n";
	
	my $factor = 4; # $factor > 1
	$max_epsilon_scaling = 2 + int( log( (1+$min_size) * $epsilon )/log($factor) ); # print "\n \$max_epsilon_scaling = $max_epsilon_scaling \n";   

	my $feasible_assignment_condition = 0;

	# The preceding observations suggest the idea of epsilon-scaling, which consists of applying the algorithm several times, 
	# starting with a large value of epsilon and successively reducing epsilon until it is less than some critical value.
   
	while( $epsilon >= 1/(1+$min_size) and $max_size >= 2 ){
   
		$epsilon_scaling++;
		$iter_count_local = 0;
		
		%assignned_object = ();
		%assignned_person = ();
		%seen_person = ();

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

 
 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 --- ###
 ### ---            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;

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

  
	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


=head1 AUTHOR

    Claudio Fernandes de Souza Rodrigues
	May 21, 2018