and 1 contributors

# NAME

```
Algorithm::Bertsekas - auction algorithm for the assignment problem.
This is a perl implementation for the auction algorithm for the assymmetric (N<=M) allocation 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."
One 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

```
use Algorithm::Bertsekas qw(auction);
my @array1 = ( 19, 74, 58, 1 )
my @array2 = ( 94, 55, 90, 45, 56, 95, 90 );
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;
}
Alternatively, we can define the matrix with its elements:
my @input_matrix = (
[ 75, 36, 71, 26, 37, 76, 71 ],
[ 20, 19, 16, 29, 18, 21, 16 ],
[ 36, 3, 32, 13, 2, 37, 32 ],
[ 93, 54, 89, 44, 55, 94, 89 ]
);
94 55 90 45 56 95 90
19 [ 75 36 71 26 37 76 71 ]
74 [ 20 19 16 29 18 21 16 ]
58 [ 36 3 32 13 2 37 32 ]
1 [ 93 54 89 44 55 94 89 ]
my ( $optimal, $assignement_ref, $output_index_ref ) = auction( matrix_ref => \@input_matrix, maximize_total_benefit => 1, verbose => 3 );
Objective --> to Maximize the total benefit
Number of left nodes: 4
Number of right nodes: 7
Number of edges: 28
Solution
Optimal assignment, sum of values = 230
Feasible assignment condition: stepsize = 0.2 < 1/4 = 0.25
Number of iterations: 18
Maximum index size = [ 0 1 2 3 4 5 6 ]
@output_index indexes = [ 5 3 6 0 2 1 4 ]
@output_index values = [76 29 32 93 ]
original matrix 4 x 7 with solution:
[ 75 36 71 26 37 76** 71 ]
[ 20 19 16 29** 18 21 16 ]
[ 36 3 32 13 2 37 32**]
[ 93** 54 89 44 55 94 89 ]
Pairs (in ascending order of weight function values):
indexes ( 1, 3 ), weight value = 29 ; sum of values = 29
indexes ( 2, 6 ), weight value = 32 ; sum of values = 61
indexes ( 0, 5 ), weight value = 76 ; sum of values = 137
indexes ( 3, 0 ), weight value = 93 ; sum of values = 230
indexes ( 4, 2 ), weight value = ; sum of values = 230
indexes ( 5, 1 ), weight value = ; sum of values = 230
indexes ( 6, 4 ), weight value = ; sum of values = 230
Common use of the solution:
foreach my $array1_index ( sort { $a <=> $b } keys %{$assignement_ref} ){
my $i = $array1_index;
my $j = $assignement_ref->{$array1_index};
...
}
for my $i ( 0 .. $#{$output_index_ref} ){
my $j = $output_index_ref->[$i];
...
}
```

# OPTIONS

```
matrix_ref => \@input_matrix, reference to array: matrix N x M.
maximize_total_benefit => 0, 0: minimize the total benefit ; 1: maximize the total benefit.
inicial_stepsize => 1, auction algorithm terminates with a feasible assignment if the problem data are integer and stepsize < 1/min(N,M).
inicial_price => 0,
verbose => 3, print messages on the screen, level of verbosity, 0: quiet; 1, 2, 3, 4, 9, 10: debug information.
```

# EXPORT

` "auction" function by default.`

# INPUT

```
The input matrix should be in a two dimensional array (array of array)
and the 'auction' subroutine expects a reference to this array.
```

# OUTPUT

```
The $output_index_ref is the reference to the output_index array.
The $assignement_ref is the reference to the assignement hash.
The $optimal is the total benefit which can be a minimum or maximum value.
```

# SEE ALSO

```
1. Dimitri P. Bertsekas - Network Optimization: Continuous and Discrete Models.
http://web.mit.edu/dimitrib/www/netbook_Full_Book.pdf
2. https://github.com/EvanOman/AuctionAlgorithmCPP/blob/master/auction.cpp
This Perl algorithm has been adapted from this implementation.
3. https://en.wikipedia.org/wiki/Assignment_problem
```

# AUTHOR

```
Claudio Fernandes de Souza Rodrigues
February 2018
Sao Paulo, Brasil
claudiofsr@yahoo.com
```

# COPYRIGHT AND LICENSE

```
Copyright (c) 2018 Claudio Fernandes de Souza Rodrigues. All rights reserved.
This program is free software; you can redistribute it and/or modify
it under the same terms as Perl itself.
```