Linear Assignment Problem Solvers

Warnings

• gotcha The package `lapx` should be imported using `import lap`. Attempting to `import lapx` will result in an `ModuleNotFoundError`.
  Fix: Always use `import lap` after installing `lapx`.
• breaking Installing both `lap` (original package) and `lapx` simultaneously will lead to conflicts, as both provide the `lap` import. The package installed last will override the other.
  Fix: Ensure only one of `lap` or `lapx` is installed in your environment. `lapx` is recommended for extended features and better performance.
• gotcha Since v0.7.1, the `lapjvs()` function defaults `prefer_float32` to `True`. While this generally improves speed without altering return results, users expecting `float64` precision by default for intermediate calculations (as in older versions) should explicitly set `prefer_float32=False`.
  Fix: If specific float precision is required for `lapjvs()`, explicitly set the `prefer_float32` parameter (e.g., `lap.lapjvs(..., prefer_float32=False)`).
• gotcha Starting from v0.8.0, dedicated batch processing functions (e.g., `lapjvx_batch`, `lapjvs_batch`) were introduced. While older single-assignment functions might still process batches in some contexts, using the explicit `_batch` functions is recommended for optimal performance and correct handling of batch inputs.
  Fix: For batch processing, transition to using the `_batch` variants of the assignment functions for clarity and performance.

Install

• pip install lapx Install from PyPI

Imports

• lap

  import lap

  The installed package is `lapx`, but it is imported as `lap` to maintain compatibility with the original `lap` library on which it is based.
• lapjv

  import lap
  result = lap.lapjv(...)

  Primary function for dense linear assignment problems.
• lapjvs

  import lap
  result = lap.lapjvs(...)

  Enhanced version of lapjv with specific optimizations.

Quickstart

This example demonstrates how to use the `lapjv` function to solve a basic linear assignment problem given a cost matrix. The function returns the optimal total cost and the assignments for rows and columns.

import lap
import numpy as np

# Example cost matrix
cost_matrix = np.array([[1, 2, 3],
                        [3, 1, 2],
                        [2, 3, 1]])

# Solve the linear assignment problem using lapjv
cost, x, y = lap.lapjv(cost_matrix)

print(f"Optimal assignment cost: {cost}")
print(f"Row assignments (x, maps row index to column index): {x}")
print(f"Column assignments (y, maps column index to row index): {y}")