{"id":4607,"library":"lap","title":"Linear Assignment Problem solver (LAPJV/LAPMOD)","description":"The 'lap' library provides a fast Python solver for the Linear Assignment Problem (LAP) using the Jonker-Volgenant algorithm for both dense (LAPJV) and sparse (LAPMOD) cost matrices. It's implemented from scratch based on original research papers. Currently at version 0.5.13, it sees active but infrequent releases, usually a few per year, ensuring ongoing maintenance and compatibility updates.","status":"active","version":"0.5.13","language":"en","source_language":"en","source_url":"https://github.com/gatagat/lap","tags":["linear assignment problem","optimization","LAPJV","LAPMOD","numpy","hungarian algorithm"],"install":[{"cmd":"pip install lap","lang":"bash","label":"Install from PyPI"}],"dependencies":[{"reason":"Required for numerical operations, specifically for representing cost matrices. `lap` v0.5.13 supports both NumPy 1.x and 2.x for Python 3.8-3.14.","package":"numpy","optional":false}],"imports":[{"note":"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.","wrong":"from lap import lapjv (indirect import)","symbol":"lapjv","correct":"import lap\ncost, x, y = lap.lapjv(C)"},{"note":"Similar to lapjv, it's typically accessed via the 'lap' module.","symbol":"lapmod","correct":"import lap\ncost, x, y = lap.lapmod(C)"}],"quickstart":{"code":"import lap\nimport numpy as np\n\n# Example for LAPJV (dense matrix)\n# C is the cost matrix, e.g., representing costs for assigning rows to columns\nC_dense = np.random.rand(4, 5) # 4 rows, 5 columns\ncost, x, y = lap.lapjv(C_dense, extend_cost=True)\nprint(f\"LAPJV Cost: {cost}\\nRow assignments (x): {x}\\nColumn assignments (y): {y}\")\n\n# Example for LAPMOD (sparse matrix) - typically faster for larger, sparse matrices\n# For simplicity, using a dense matrix here, but 'lapmod' is optimized for sparse inputs.\n# Note: lapmod primarily expects square matrices for direct use, consider extensions for non-square.\nC_sparse_example = np.array([\n    [1, np.inf, 3, np.inf],\n    [np.inf, 2, np.inf, 4],\n    [5, np.inf, 6, np.inf],\n    [np.inf, 7, np.inf, 8]\n])\n\ncost_mod, x_mod, y_mod = lap.lapmod(C_sparse_example)\nprint(f\"\\nLAPMOD Cost: {cost_mod}\\nRow assignments (x): {x_mod}\\nColumn assignments (y): {y_mod}\")","lang":"python","description":"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."},"warnings":[{"fix":"Ensure a compatible C++ compiler is installed and properly configured in your environment. For Windows, install 'Microsoft C++ Build Tools' from Visual Studio.","message":"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.","severity":"gotcha","affected_versions":"<0.5.13, potentially all versions for source build"},{"fix":"Consider the characteristics of your cost matrix (size, density) when choosing between `lap.lapjv` and `lap.lapmod` to optimize performance.","message":"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.","severity":"gotcha","affected_versions":"All versions"},{"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.","message":"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`).","severity":"gotcha","affected_versions":"All versions"},{"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.","message":"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.","severity":"gotcha","affected_versions":"All versions"}],"env_vars":null,"last_verified":"2026-04-12T00:00:00.000Z","next_check":"2026-07-11T00:00:00.000Z"}