%%% auction


%=================================================================================

function [colsol, rowsol] = auction(assignCost)

%function [colsol, rowsol] = auction(assignCost, guard)
%AUCTION : performs assignment using Bertsekas' auction algorithm
%          The auction is 1-sided and uses a fixed epsilon.
%  colsol = auction(assignCost) returns column assignments: colsol(j) gives the
%           row assigned to column j.
%
%           assignCost is an m x n matrix of costs for associating each row
%           with each column.  m >= n (rectangular assignment is allowed).
%           Auction finds the assignment that minimizes the costs.
%
%  colsol = auction(assignCost, guard) sets the cost of column
%           non-assignment = guard.  All assignments will have cost < guard.
%           A column will not be assigned if the savings from eliminating it
%           exceeds the guard cost.  colsol(j) = 0 indicates that the optimal
%           solution does not assign column j to any row.
%
%  [colsol,rowsol] = auction(assignCost) also returns the row assignments:
%           rowsol(i) gives the column assigned to row j.
%
%  Reference
%  Bertsekas, D. P., "The Auction Algorithm: A Distributed Relaxation Method
%  for the Assignment Problem," Annals of Operations Research, 14, 1988, pp.
%  103-123.

% Mark Levedahl
% 
%=================================================================================

[m,n] = size(assignCost);

if m < n
	error('cost matrix must have no more columns than rows.')
end

% augment cost matrix with a guard row if specified.
m0 = m;
% if isfinite(guard) %%% DONE BY JS
% 	m = m+1;
% 	assignCost(m,:) = guard;
% end

% init return arrays
colsol = zeros(1,n);
rowsol = zeros(m,1);
price = zeros(m,1);
EPS = sqrt(eps) / (n+1);

% 1st step is a full parallel solution.  Get bids for all columns
jp = 1:n;
f = assignCost;
[b1,ip] = min(f);                   % cost and row of best choice
f(ip + m*(0:n-1)) = inf;            % eliminate best from contention
bids = min(f) - b1;                 % cost of runner up choice hence bid

% Arrange bids so highest (best) are last and will overwrite the lower bids.
[tmp,ibid] = sort(bids(:));

% Now assign best bids (lesser bids are overwritten by better ones).
price(ip(ibid)) = price(ip(ibid)) + EPS + tmp;
rowsol(ip(ibid)) = jp(ibid);        % do row assignments
iy = find(rowsol);
colsol(rowsol(iy)) = iy;            % map to column assignments

% The guard row cannot be assigned (always available)
if m0 < m
	price(m) = 0;
	rowsol(m) = 0;
end

% Now Continue with non-parallel code handling any contentions.
while ~all(colsol)
	for jp = find(~colsol)
		f = assignCost(:,jp) + price;   % costs
		[b1,ip] = min(f);               % cost and row of best choice
		if ip > m0
			colsol(jp) = m;
		else
			f(ip) = inf;                    % eliminate from contention
			price(ip) = price(ip) + EPS + min(f) - b1; % runner up choice hence bid
			if rowsol(ip)                   % take the row away if already assigned
				colsol(rowsol(ip)) = 0;
			end
			rowsol(ip) = jp;                % update row and column assignments
			colsol(jp) = ip;
		end % if ip == m
	end
end

% screen out infeasible assignments
if m > m0
	colsol(colsol == m) = 0;
	rowsol(m) = [];
end

%=================================================================================