auction_match: Compute optimal (maximal) weighted assignment
% and the corresponding "lattice of dual prices" supporting the
% optimal assignment.
% auction_match(disMatrix) computes the optimal assignment for the
% given rectangular value matrix, for example the assignment
% of bidders (in rows) to objects (in columns) and vice versa.
% [assignment,r,p,u,v,value] = ASSIGNMENTOPTIMAL(DISTMATRIX) returns the assignment
% vector (in assignment) and the overall value (in value) and
% v: surplus of columns if columns were bidding for rows.
% u: the corresponding prices of rows.
% p: prices for columns if rows were bidding for columns
% r: the corresponding surplus of rows.
% Note that (p,-r) forms the lower corner and (v,-u) forms the
% upper corner in the lattice of optimal dual vector supporting
% the optimal assignment thus giving the complete lattice.
% Ref. the survey "From the Assignment Model to Combinatorial Auctions"
% by S. Bikhchandani and J. Ostroy
% This is update of the assignment code by Markus Buehren which used Munkres
% Algorithm for MINIMAL weighted matching. A description of Munkres algorithm
% (also called Hungarian algorithm) can easily be found on the web.
Anuj Kumar (2021). Rectangular maximal assignment with lattice of dual price (https://www.mathworks.com/matlabcentral/fileexchange/14251-rectangular-maximal-assignment-with-lattice-of-dual-price), MATLAB Central File Exchange. Retrieved .
The result is wrong! With this test: distMatrix = [65 75 26 91 44 9; 5 59 6 33 74 39; 33 60 92 37 82 35; 97 76 47 50 21 84; 53 52 1 44 55 84; 85 67 86 46 13 76]; The output assignment is: [4 5 3 1 6 2] (totalcost = 505). But the optimal assignment is: [6 1 2 4 3 5] (total cost = 138).
Inspired by: Functions for the rectangular assignment problem
Find the treasures in MATLAB Central and discover how the community can help you!Start Hunting!