assignment: Linear assignment solver

In couplr: Optimal Pairing and Matching via Linear Assignment

Linear assignment solver

Description

Solve the linear assignment problem (minimum- or maximum-cost matching) using several algorithms. Forbidden edges can be marked as NA or Inf.

Usage

assignment(
  cost,
  maximize = FALSE,
  method = c("auto", "jv", "hungarian", "auction", "auction_gs", "auction_scaled", "sap",
    "ssp", "csflow", "hk01", "bruteforce", "ssap_bucket", "cycle_cancel", "gabow_tarjan",
    "lapmod", "csa", "ramshaw_tarjan", "push_relabel", "orlin", "network_simplex"),
  auction_eps = NULL,
  eps = NULL
)

Arguments

cost	Numeric matrix; rows = tasks, columns = agents. NA or Inf entries are treated as forbidden assignments.
maximize	Logical; if TRUE, maximizes the total cost instead of minimizing.
method	Character string indicating the algorithm to use. Options: General-purpose solvers: "auto" — Automatic selection based on problem characteristics (default) "jv" — 'Jonker-Volgenant', fast general-purpose O(n³) "hungarian" — Classic 'Hungarian' algorithm O(n³) Auction-based solvers: "auction" — 'Bertsekas' auction with adaptive epsilon "auction_gs" — 'Gauss-Seidel' variant, good for spatial structure "auction_scaled" — 'Epsilon-scaling', fastest for large dense problems Specialized solvers: "sap" / "ssp" — Shortest augmenting path, handles sparsity well "lapmod" — Sparse JV variant, faster when >50\ "hk01" — 'Hopcroft-Karp' for binary (0/1) costs only "ssap_bucket" — 'Dial' algorithm for integer costs "line_metric" — O(n log n) for 1D assignment problems "bruteforce" — Exact enumeration for tiny problems (n <= 8) Advanced solvers: "csa" — 'Goldberg-Kennedy' cost-scaling, often fastest for medium-large "gabow_tarjan" — 'Gabow-Tarjan' bit-scaling with complementary slackness O(n³ log C) "cycle_cancel" — Cycle-canceling with 'Karp' algorithm "csflow" — Cost-scaling network flow "network_simplex" — 'Network simplex' with spanning tree representation "orlin" — 'Orlin-Ahuja' scaling O(sqrt(n) * m * log(nC)) "push_relabel" — 'Push-relabel' max-flow based solver "ramshaw_tarjan" — 'Ramshaw-Tarjan', optimized for rectangular matrices (n != m)
auction_eps	Optional numeric epsilon for the 'Auction'/'Auction-GS' methods. If NULL, an internal default (e.g., 1e-9) is used.
eps	Deprecated. Use auction_eps. If provided and auction_eps is NULL, its value is used for auction_eps.

Details

method = "auto" selects an algorithm based on problem size/shape and data characteristics:

• Very small (n <= 8): "bruteforce" — exact enumeration

• Binary/constant costs: "hk01" — specialized for 0/1 costs

• Large sparse (n>100, >50\

• Sparse or very rectangular: "sap" — handles sparsity well

• Small-medium (8 < n <= 50): "hungarian" — provides exact dual solutions

• Medium (50 < n <= 75): "jv" — fast general-purpose solver

• Large (n>75): "auction_scaled" — fastest for large dense problems

Benchmarks show 'Auction-scaled' and 'JV' are 100-1500x faster than 'Hungarian' at n=500.

Value

An object of class lap_solve_result, a list with elements:

• match — integer vector of length min(nrow(cost), ncol(cost)) giving the assigned column for each row (0 if unassigned).

• total_cost — numeric scalar, the objective value.

• status — character scalar, e.g. "optimal".

• method_used — character scalar, the algorithm actually used.

See Also

• lap_solve() — Tidy interface returning tibbles

• lap_solve_kbest() — Find k-best assignments ('Murty' algorithm)

• assignment_duals() — Extract dual variables for sensitivity analysis

• bottleneck_assignment() — Minimize maximum edge cost (minimax)

• sinkhorn() — Entropy-regularized optimal transport

Examples

cost <- matrix(c(4,2,5, 3,3,6, 7,5,4), nrow = 3, byrow = TRUE)
res  <- assignment(cost)
res$match; res$total_cost

couplr documentation built on Jan. 20, 2026, 5:07 p.m.