assignment.auction_assignment
def auction_assignment(cost_matrix: torch.Tensor, bid_size: float, max_iters: int = 100000) -> tuple[torch.Tensor, torch.Tensor, torch.Tensor]Solve a linear assignment problem using Bertsekas' auction algorithm.
Converts the cost matrix to a profit matrix, then runs synchronous
bidding until every row (or every column, for rectangular problems) is
assigned. Non-finite entries mark forbidden pairs and are penalised
internally so the solver never selects them.
Parameters
| Name | Type | Description |
|---|---|---|
| cost_matrix | torch.Tensor | ``(N, M)`` cost matrix. ``+inf`` entries mark forbidden pairs. NaN and ``-inf`` are rejected. |
| bid_size | float | Auction bid step size. The internal ``epsilon`` is derived as ``min(bid_size / min(N, M), 1e-3)``. |
| max_iters = 100000 | int | Maximum number of bidding iterations. Raises ``RuntimeError`` if the algorithm has not converged within this budget. |
Returns
torch.Tensor — ``(K, 2)`` long tensor of matched ``(row, col)`` indices.
Source: torchmatch/assignment/_auction.py:10