Algorithm-Bertsekas
view release on metacpan or search on metacpan
my @input_matrix = (
[ 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 ]
);
my ( $optimal, $assignment_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: 10
Number of right nodes: 10
Number of edges: 100
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 ]
Pairs (in ascending order of matrix values):
indexes ( 8, 7 ), matrix value = 75 ; sum of values = 75
indexes ( 1, 0 ), matrix value = 76 ; sum of values = 151
indexes ( 4, 9 ), matrix value = 81 ; sum of values = 232
indexes ( 7, 4 ), matrix value = 88 ; sum of values = 320
indexes ( 3, 8 ), matrix value = 90 ; sum of values = 410
indexes ( 9, 3 ), matrix value = 90 ; sum of values = 500
indexes ( 0, 5 ), matrix value = 95 ; sum of values = 595
indexes ( 5, 6 ), matrix value = 99 ; sum of values = 694
indexes ( 6, 2 ), matrix value = 99 ; sum of values = 793
indexes ( 2, 1 ), matrix value = 100 ; sum of values = 893
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, 5, 8, 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 $assignment_ref is the reference to the assignment hash.
The $optimal is the total benefit which can be a minimum or maximum value.
SEE ALSO
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
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.
( run in 1.156 second using v1.01-cache-2.11-cpan-0bd6704ced7 )