jonker volgenant algorithm for linear assignment problem

• Get started
• Function reference
• Tree distance analysis
• Calculate tree similarity with 'TreeDist'
• Contextualizing tree distances
• Trees with different leaves
• Tree space analysis
• Analysing landscapes of phylogenetic trees
• Comparing sets of trees from different analyses
• Tree distance introductions
• Comparing splits using information theory
• Extending the Robinson-Foulds metric
• Generalized Robinson-Foulds distances

Solve linear assignment problem using LAPJV

Use the algorithm of Jonker and Volgenant (1987) to solve the Linear Sum Assignment Problem .

Matrix of costs.

LAPJV() returns a list with two entries: score , the score of the optimal matching; and matching , the columns matched to each row of the matrix in turn.

The Linear Assignment Problem seeks to match each row of a matrix with a column, such that the cost of the matching is minimized.

The Jonker & Volgenant approach is a faster alternative to the Hungarian algorithm (Munkres 1957) , which is implemented in clue::solve_LSAP() .

Note: the JV algorithm expects integers. In order to apply the function to a non-integer n , as in the tree distance calculations in this package, each n is multiplied by the largest available integer before applying the JV algorithm. If two values of n exhibit a trivial difference -- e.g. due to floating point errors -- then this can lead to interminable run times. (If numbers of the magnitude of billions differ only in their last significant digit, then the JV algorithm may undergo billions of iterations.) To avoid this, integers over 2^22 that differ by a value of 8 or less are treated as equal.

Jonker R, Volgenant A (1987). “A shortest augmenting path algorithm for dense and sparse linear assignment problems.” Computing , 38 , 325--340. doi:10.1007/BF02278710 . Munkres J (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics , 5 (1), 32--38. doi:10.1137/0105003 .

Implementations of the Hungarian algorithm exist in adagio , RcppHungarian , and clue and lpSolve ; for larger matrices, these are substantially slower. (See discussion at Stack Overflow .)

The JV algorithm is implemented for square matrices in the Bioconductor package GraphAlignment::LinearAssignment() .

C++ code by Roy Jonker, MagicLogic Optimization Inc. [email protected] , with contributions from Yong Yang [email protected] , after Yi Cao

A shortest augmenting path algorithm for dense and sparse linear assignment problems

Ein Algorithmus mit kürzesten alternierenden Wegen für dichte und dünne Zuordnungsprobleme

• Contributed Papers
• Published: December 1987
• Volume 38 , pages 325–340, ( 1987 )

Cite this article

• R. Jonker 1   nAff2 &
• A. Volgenant 1  

5328 Accesses

755 Citations

16 Altmetric

Explore all metrics

We develop a shortest augmenting path algorithm for the linear assignment problem. It contains new initialization routines and a special implementation of Dijkstra's shortest path method. For both dense and sparse problems computational experiments show this algorithm to be uniformly faster than the best algorithms from the literature. A Pascal implementation is presented.

Zusammenfassung

Wir entwickeln einen Algorithmus mit kürzesten alternierenden Wegen für das lineare Zuordnungsproblem. Er enthält neue Routinen für die Anfangswerte und eine spezielle Implementierung der Kürzesten-Wege-Methode von Dijkstra. Sowohl für dichte als auch für dünne Probleme zeigen Testläufe, daß unser Algorithmus gleichmäßig schneller als die besten Algorithmen aus der Literatur ist. Eine Implementierung in Pascal wird angegeben.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Efficient Algorithms for Geometric Shortest Path Query Problems

Practical Algorithms for the All-Pairs Shortest Path Problem

On the Quadratic Shortest Path Problem

Balinski, M. L.: Signature methods for the assignment problem. Operations Research 33 , 527–536 (1985).

Google Scholar  

Barr, R., Glover, F., Klingman, D.: The alternating path basis algorithm for assignment problems. Mathematical Programming 13 , 1–13 (1977).

Article   Google Scholar  

Bertsekas, D. P.: A new algorithm for the linear assignment problem. Mathematical Programming 21 , 152–171 (1981).

Burkard, R. E., Derigs, U.: Assignment and Matching Problems: Solution Methods with Fortran Programs, pp. 1–11. Berlin-Heidelberg-New York: Springer 1980.

Carpaneto, G., Toth, P.: Algorithm 548 (solution of the assignment problem). ACM Transactions on Mathematical Software 6 , 104–111 (1980).

Carpaneto, G., Toth, P.: Algorithm 50: algorithm for the solution of the assignment problem for sparse matrices. Computing 31 , 83–94 (1983).

Carraresi, P., Sodini, C.: An efficient algorithm for the bipartite matching problem. European Journal of Operational Research 23 , 86–93 (1986).

Derigs, U., Metz, A.: An efficient labeling technique for solving sparse assignment problems. Computing 36 , 301–311 (1986).

Derigs, U., Metz, A.: An in-core/out-of-core method for solving large scale assignment problems. Zeitschrift für Operations Research 30 , 181–195 (1986).

Dorhout, B.: Het Lineaire Toewijzingsprobleem: Vergelijking van Algorithmen. Rapport BN 21/73, Mathematisch Centrum, Amsterdam (1973).

Dorhout, B.: Experiments with some algorithms for the linear assignment problem. Report BW 39, Mathematisch Centrum, Amsterdam (1975).

Dijkstra, E. W.: A note on two problems in connexion with graphs. Numerische Mathematik 1 , 269–271 (1959).

Edmonds, J., Karp, R. M.: Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM 19 , 248–264 (1972).

Ford jr., L. R., Fulkerson, D. R.: Flows in Networks. Princeton: Princeton University Press 1962.

Glover, F., Klingman, D., Phillips, N.: A new polynomially bounded shortest path algorithm. Operations Research 33 , 65–73 (1985).

Glover, F., Klingman, D., Phillips, N., Schneider, R.: New polynomial shortest path algorithms and their computational attributes. Management Science 31 , 1106–1128 (1985).

Goldfarb, D.: Efficient dual simplex algorithms for the assignment problem. Mathematical Programming 33 , 187–203 (1985).

Hung, M. S., Rom, W. O.: Solving the assignment problem by relaxation. Operations Research 28 , 969–982 (1980).

Jonker, R.: Traveling salesman and assignment algorithms: design and implementation. Faculty of Actuarial Science and Econometrics, University of Amsterdam (1986).

Jonker, R., Volgenant, A.: Improving the Hungarian assignment algorithm. Operations Research Letters 5 , 171–175 (1986).

Karp, R. M.: An algorithm to solve the m×n assignment problem in expected time O ( mn log n ). Networks 10 , 143–152 (1980).

Kuhn, H. W.: The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2 , 83–97 (1955).

Lawler, E. L.: Combinatorial Optimization: Networks and Matroids. New York: Holt, Rinehart & Winston 1976.

Mack, C.: The Bradford method for the assignment problem. New Journal of Statistics and Operational Research 1 , 17–29 (1969).

McGinnis, L. F.: Implementation and testing of a primal-dual algorithm for the assignment problem. Operations Research 31 , 277–291 (1983).

Papadimitriou, C. H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Englewood Cliffs, N. J.: Prentice-Hall 1982.

Silver, R.: An algorithm for the assignment problem. Communications of the ACM 3 , 605–606 (1960).

Tabourier, Y.: Un Algorithme pour le Problème d'Affectation. R.A.I.R.O. Recherche Opérationnelle/Operations Research 6 , 3–15 (1972).

Tomizawa, N.: On some techniques useful for the solution of transportation problems. Networks 1 , 173–194 (1971).

Download references

Author information

Present address: Koninklyke/Shell-Laboratorium, Amsterdam, The Netherlands

Authors and Affiliations

Faculty of Actuarial Sciences and Econometrics, University of Amsterdam, Jodenbreestraat 23, 1011 NH, Amsterdam, The Netherlands

R. Jonker & A. Volgenant

You can also search for this author in PubMed   Google Scholar

Rights and permissions

Reprints and permissions

About this article

Jonker, R., Volgenant, A. A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38 , 325–340 (1987). https://doi.org/10.1007/BF02278710

Download citation

Received : 06 May 1986

Issue Date : December 1987

DOI : https://doi.org/10.1007/BF02278710

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

AMS Subject Classifications

• Linear assignment problem
• shortest path methods
• Pascal implementation
• Find a journal
• Publish with us
• Track your research

Solve linear assignment problem using LAPJV

Description.

Use the algorithm of Jonker and Volgenant (1987) to solve the Linear Sum Assignment Problem .

The Linear Assignment Problem seeks to match each row of a matrix with a column, such that the cost of the matching is minimized.

The Jonker & Volgenant approach is a faster alternative to the Hungarian algorithm (Munkres 1957), which is implemented in clue::solve_LSAP() .

Note: the JV algorithm expects integers. In order to apply the function to a non-integer n , as in the tree distance calculations in this package, each n is multiplied by the largest available integer before applying the JV algorithm. If two values of n exhibit a trivial difference – e.g. due to floating point errors – then this can lead to interminable run times. (If numbers of the magnitude of billions differ only in their last significant digit, then the JV algorithm may undergo billions of iterations.) To avoid this, integers over 2^22 that differ by a value of 8 or less are treated as equal.

LAPJV() returns a list with two entries: score , the score of the optimal matching; and matching , the columns matched to each row of the matrix in turn.

C++ code by Roy Jonker, MagicLogic Optimization Inc. [email protected] , with contributions from Yong Yang [email protected] , after Yi Cao

Jonker R, Volgenant A (1987). “A shortest augmenting path algorithm for dense and sparse linear assignment problems.” Computing , 38 , 325–340. doi:10.1007/BF02278710 . Munkres J (1957). “Algorithms for the assignment and transportation problems.” Journal of the Society for Industrial and Applied Mathematics , 5 (1), 32–38. doi:10.1137/0105003 .

Implementations of the Hungarian algorithm exist in adagio , RcppHungarian , and clue and lpSolve ; for larger matrices, these are substantially slower. (See discussion at Stack Overflow .)

The JV algorithm is implemented for square matrices in the Bioconductor package GraphAlignment::LinearAssignment() .

• Previous Article
• Next Article

The Jonker-Volgenant algorithm applied to click-train separation

Author to whom correspondence should be addressed. Electronic mail: [email protected]

• Article contents
• Figures & tables
• Supplementary Data
• Peer Review
• Reprints and Permissions
• Cite Icon Cite
• Search Site

Paul M. Baggenstoss; The Jonker-Volgenant algorithm applied to click-train separation. J. Acoust. Soc. Am. 1 May 2014; 135 (5): 2485–2488. https://doi.org/10.1121/1.4869677

Download citation file:

• Ris (Zotero)
• Reference Manager

The problem of click-train separation is cast as a linear assignment problem to obtain a faster solution guaranteed to achieve the global minimum error. It is shown how the problem can be cast in a compact matrix form that is solvable by an off-the-shelf algorithm, the Jonker-Volgenant algorithm.

Sign in via your Institution

Citing articles via.

• Online ISSN 1520-8524
• Print ISSN 0001-4966
• For Researchers
• For Librarians
• For Advertisers
• Our Publishing Partners  
• Physics Today
• Conference Proceedings
• Special Topics

pubs.aip.org

• Privacy Policy
• Terms of Use

Connect with AIP Publishing

This feature is available to subscribers only.

Sign In or Create an Account

pylapy 0.1.1

pip install pylapy Copy PIP instructions

Released: Apr 26, 2024

Pythonic wrapper around Linear Assignement Problem solvers

Verified details

Maintainers.

Unverified details

Project links, github statistics.

• Open issues:

View statistics for this project via Libraries.io , or by using our public dataset on Google BigQuery

License: MIT License (MIT)

Author: Raphael Reme

Tags lap, linear programming, optimization, association problem

Requires: Python >=3.7

Classifiers

• OSI Approved :: MIT License
• OS Independent
• Python :: 3.7
• Python :: 3.8
• Python :: 3.9
• Python :: 3.10
• Python :: 3.11
• Python :: 3.12

Project description

We provide a solver for the assignement problem with Hungarian algorithm (Jonker-Volgenant variants [1])

The main class ( pylapy.LapSolver ) is a wrapper around different implementations you can find in python: lap, lapjv, scipy, lapsolver [2, 3, 4, 5].

It unifies the functionality of each implementation and allows you to use the one which is the fastest on your problem. Note that to solve the same problem, an implementation/method can be more than 10 times slower than an other one.

It also helps you to handle non square matrices and setting a soft threshold on assignements (usually leads to better performances than hard thresholding).

We provide some benchmark (but they are a bit hard to read and messy). Given your lap problem, try to make it work with the simplest implementation (scipy) and then (if needed) try to install lap or lapjv and see if they yield better computational performances.

As of today, lapjv do not support macos, lapsolver do not support python > 3.10. We now use lapx which distributes correctly the lap package.

Getting started

We provide several scripts (and corresponding plots) in the benchmark/ folder. They compare different implementations and dist extensions (for non square matrix or soft thresholding). We have only tested them on a intel core i7 with Ubuntu 20.04 and python 3.10. Thus we do not guarantee that the choice we make by default are the fastest for you.

Lapjv seems to usually outperform other implementations (Up to 2 times faster). Lap and Scipy are also pretty fast and can sometimes be faster than Lapjv. Lapsolver is usually much slower and should be avoided.

To handle soft thresholding and non-square matrices, we use by default the fastest options of our benchmark. This can be changed by setting LapSolver.cost_extension and LapSolver.shape_extension .

Handling non square matrices

With a rectangular assignment problem, you have to extend the distance matrix into a square one. There are multiple ways to perform this shape extension. All yield the same final links and cost some are much faster/slower than others.

We provide several shape extension functions and benchmark them. By default, the solver uses the fastest one for the implementation you use. You can build your own or enforce another one by setting the LapSolver.shape_extension attribute. Please have a look at shape_extension module and benchmark_shape_extension script for more details.

According to our benchmark, we use smallest_fill_inf for scipy [4] and smallest_fill_0 for other implementations. (Note that lap [2] provide its own implementation displayed as ref here.)

Handling soft thresholding

Rather than applying hard thresholding and cut links that are above a threshold eta , it is common and usually better to assign a row or a column to "no one" with a cost eta . This is done by adding "sink" rows and columns. When a true row/column is linked to a "sink" column/row, it is considered non linked.

Adding these sink nodes can also be done multiple ways resulting in equivalent links/cost but different run time. We provide several cost extension functions and benchmark them. By default, the solver uses the expected fastest one for the implementation you use. You can build your own extension or enforce another one by setting the LapSolver.cost_extension attribute. Please have a look at cost_extension module and benchmark_cost_extension script for more details.

It is less obvious to descriminate between the cost extension functions (Even more if you add sparsity: more plots in benchmark/images/cost_extension ). Nonetheless, we decided to go with diag_split_cost for lapsolver [5] and row_cost for other implementations that usually leads to the best performances.

Choosing the implementations

First, some implementations are not available on some operating system or python version, our wrapper allows you to switch between implementations without changing your code. It seems that for instance, lap is not available for python 3.6, lapjv is not available in macOs, etc.

Also you want to choose the fastest one for your problem. We have compared all implementations on several cases (using sparsity, rectangular problems, and cost limit):

It seems that lapjv is usually faster than other implementations. Scipy and lap are also pretty fast and can be faster than lapjv depending on your use case. Lapsolver is always outperformed and should be avoided.

We have also tested lapmod from lap [2] for sparse matrices. It can sometimes be faster than other implementations but it is less stable and we do not add the support of this algorithm in the wrapper. (Note that for unfeasible problems, it yields a segfault).

Warning: For rectangular matrices, lapjv seems to sometimes output a non-optimal cost (though very close to the optimal one)

• [1] R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987)
• [2] "lap: Linear Assignment Problem solver", https://github.com/gatagat/lap (Now maintained at https://github.com/rathaROG/lapx )
• [3] "lapjv: Linear Assignment Problem solver using Jonker-Volgenant algorithm", https://github.com/src-d/lapjv
• [4] "scipy: linear_sum_assignment", https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment
• [5] "py-lapsolver", https://github.com/cheind/py-lapsolver

Project details

Release history release notifications | rss feed.

Apr 26, 2024

Oct 4, 2023

Mar 27, 2023

Mar 17, 2023

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages .

Source Distribution

Uploaded Apr 26, 2024 Source

Built Distribution

Uploaded Apr 26, 2024 Python 3

Hashes for pylapy-0.1.1.tar.gz

Hashes for pylapy-0.1.1-py3-none-any.whl.

• português (Brasil)

Supported by

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Linear assignment problem solving using Jonker Volgenant Castanon method (JVC), Mack and Hungarian(Munkres) method.

Contributors 2

scipy.optimize.linear_sum_assignment #

Solve the linear sum assignment problem.

The cost matrix of the bipartite graph.

Calculates a maximum weight matching if true.

An array of row indices and one of corresponding column indices giving the optimal assignment. The cost of the assignment can be computed as cost_matrix[row_ind, col_ind].sum() . The row indices will be sorted; in the case of a square cost matrix they will be equal to numpy.arange(cost_matrix.shape[0]) .

for sparse inputs

The linear sum assignment problem [1] is also known as minimum weight matching in bipartite graphs. A problem instance is described by a matrix C, where each C[i,j] is the cost of matching vertex i of the first partite set (a ‘worker’) and vertex j of the second set (a ‘job’). The goal is to find a complete assignment of workers to jobs of minimal cost.

Formally, let X be a boolean matrix where \(X[i,j] = 1\) iff row i is assigned to column j. Then the optimal assignment has cost

where, in the case where the matrix X is square, each row is assigned to exactly one column, and each column to exactly one row.

This function can also solve a generalization of the classic assignment problem where the cost matrix is rectangular. If it has more rows than columns, then not every row needs to be assigned to a column, and vice versa.

This implementation is a modified Jonker-Volgenant algorithm with no initialization, described in ref. [2] .

Added in version 0.17.0.

https://en.wikipedia.org/wiki/Assignment_problem

DF Crouse. On implementing 2D rectangular assignment algorithms. IEEE Transactions on Aerospace and Electronic Systems , 52(4):1679-1696, August 2016, DOI:10.1109/TAES.2016.140952