Linear Assignment Problem solver (LAPJV/LAPMOD)

Warnings

• gotcha When building `lap` from source (e.g., if pre-built wheels are unavailable or a custom environment requires it), a C++ compiler (like Microsoft Visual C++ 14.0 or greater on Windows) is required.
  Fix: Ensure a compatible C++ compiler is installed and properly configured in your environment. For Windows, install 'Microsoft C++ Build Tools' from Visual Studio.
• gotcha The `lapmod` solver is generally faster than `lapjv` for very large matrices (side > ~5000) that are also sparse (<50% finite coefficients). For smaller or denser matrices, `lapjv` might be preferred or perform similarly.
  Fix: Consider the characteristics of your cost matrix (size, density) when choosing between `lap.lapjv` and `lap.lapmod` to optimize performance.
• gotcha The `lap.lapmod` function directly supports only square matrices. For non-square assignment problems, it's crucial to transform the cost matrix into a square form (e.g., by padding with infinite costs or using `extend_cost=True` with `lapjv`).
  Fix: For non-square matrices, either use `lap.lapjv(C, extend_cost=True)` or manually pad your sparse matrix to make it square before passing it to `lap.lapmod`. Libraries like `pylapy` can provide wrappers for more flexible sparse matrix handling.
• gotcha The `lap` library expects a cost matrix where `np.inf` or large numbers represent prohibitive costs for assignments. Incorrectly using `0` or negative numbers for non-assignment costs can lead to unexpected results or incorrect optimal assignments.
  Fix: Ensure that non-assignable pairs have a cost of `np.inf` (or a sufficiently large number) in your cost matrix, and that valid assignment costs are non-negative.

Install

• pip install lap Install from PyPI

Imports

• lapjv

  import lap
  cost, x, y = lap.lapjv(C)

  While 'from lap import lapjv' might work, the common and recommended practice in documentation is to 'import lap' and access functions via the module name to avoid name clashes and clarify origin.
• lapmod

  import lap
  cost, x, y = lap.lapmod(C)

  Similar to lapjv, it's typically accessed via the 'lap' module.

Quickstart

This quickstart demonstrates how to use `lap.lapjv` for dense cost matrices and `lap.lapmod` for sparse matrices. `lapjv` can handle non-square matrices directly with `extend_cost=True`. `lapmod` is typically optimized for large, sparse *square* matrices; for non-square sparse problems, additional pre-processing or wrapper libraries might be needed.

import lap
import numpy as np

# Example for LAPJV (dense matrix)
# C is the cost matrix, e.g., representing costs for assigning rows to columns
C_dense = np.random.rand(4, 5) # 4 rows, 5 columns
cost, x, y = lap.lapjv(C_dense, extend_cost=True)
print(f"LAPJV Cost: {cost}\nRow assignments (x): {x}\nColumn assignments (y): {y}")

# Example for LAPMOD (sparse matrix) - typically faster for larger, sparse matrices
# For simplicity, using a dense matrix here, but 'lapmod' is optimized for sparse inputs.
# Note: lapmod primarily expects square matrices for direct use, consider extensions for non-square.
C_sparse_example = np.array([
    [1, np.inf, 3, np.inf],
    [np.inf, 2, np.inf, 4],
    [5, np.inf, 6, np.inf],
    [np.inf, 7, np.inf, 8]
])

cost_mod, x_mod, y_mod = lap.lapmod(C_sparse_example)
print(f"\nLAPMOD Cost: {cost_mod}\nRow assignments (x): {x_mod}\nColumn assignments (y): {y_mod}")