Skip to contents

Linear assignment solver

Source: R/lap_solve.R
assignment.Rd

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", "munkres", "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,
  memory_mode = "auto"
)

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^3) with warm-start

  • "hungarian" — Classic 'Hungarian' (shortest augmenting path) O(n^3)

  • "munkres" — Matrix-form 'Kuhn-Munkres' O(n^4), reference implementation

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

  • "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^3 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)

One-dimensional problems have their own entry point, lap_solve_line_metric(), which takes two point vectors rather than a cost matrix and runs in O(n log n).

Under "auto", a single pass over cost supplies the facts the following rules need, and the first matching rule wins:

  1. at most 8 rows and 8 columns: "bruteforce", exact and faster than setting up a general solver;

  2. finite entries all equal, or all either 0 or 1: "hk01", which exploits the absence of a real cost scale;

  3. more than half the entries non-finite: "lapmod", which carries forbidden edges in its adjacency structure;

  4. at least 3 times as many columns as rows: "sap", avoiding the padding a square-oriented solver would need;

  5. everything else: "jv".

Naming a method skips the pass. Rectangular problems are transposed internally so the solver always sees at least as many columns as rows, and the assignment is mapped back afterwards.

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.

memory_mode

One of "auto" (default), "dense", or "lazy". cost is already a materialized matrix by the time it reaches assignment(), so "auto" here is diagnostic only: it warns if the matrix is large relative to free system RAM (nothing else can be done post-hoc once the matrix already exists – build it via compute_distances(memory_mode = ...) instead to avoid materializing it in the first place). No lazy solver exists yet, so memory_mode = "lazy" currently always errors.

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.

Details

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

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

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

  • Sparse (>50\

  • Very rectangular (m >= 3n): "sap" — handles rectangular well

  • Otherwise: "jv" — fastest general-purpose solver at every size

The other solvers are available by naming them explicitly.

See also

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