linear assignment problem jonker volgenant

• 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

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() .

• By logging in you accept our terms of service and privacy policy

lapjv Release 1.3.24

Release 1.3.24 toggle dropdown 1.3.24 1.3.22 1.3.21 1.3.20 1.3.19 1.3.18 1.3.17 1.3.16 1.3.15 1.3.14.

Linear sum assignment problem solver using Jonker-Volgenant algorithm.

Homepage PyPI C++

Documentation

Linear Assignment Problem solver using Jonker-Volgenant algorithm

This project is the rewrite of pyLAPJV which supports Python 3 and updates the core code. The performance is twice as high as the original thanks to the optimization of the augmenting row reduction phase using Intel AVX2 intrinsics. It is a native Python 3 module and does not work with Python 2.x, stick to pyLAPJV otherwise.

Linear assignment problem is the bijection between two sets with equal cardinality which optimizes the sum of the individual mapping costs taken from the fixed cost matrix. It naturally arises e.g. when we want to fit t-SNE results into a rectangular regular grid. See this awesome notebook for the details about why LAP matters: CloudToGrid .

Jonker-Volgenant algorithm is described in the paper:

R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing , vol. 38, pp. 325-340, 1987.

This paper is not publicly available though a brief description exists on sciencedirect.com . JV is faster in than the Hungarian algorithm in practice, though the complexity is the same - O(n 3 ).

The C++ source of the algorithm comes from http://www.magiclogic.com/assignment.html It has been reworked and partially optimized with OpenMP 4.0 SIMD.

Tested on Linux and Windows. macOS is not supported, please do not report macOS build errors in the issues. Feel free to PR macOS support, but I warn that it will be a rough ride.

Refer to test.py for the complete code.

The assignment matrix by row is row_ind : the value at n-th place is the assigned column index to the n-th row. col_ind is the reverse of row_ind : mapping from columns to row indexes.

Note: a bijection is only possible for sets with equal cardinality. If you need to map A vectors to B vectors, derive the square symmetric (A+B) x (A+B) matrix: take the first A rows and columns from A and the remaining [A..A+B] rows and columns from B. Set the A->A and B->B costs to some maximum distance value, big enough so that you don't see assignment errors.

Illegal instruction

This error appears if your CPU does not support the AVX2 instruction set. We do not ship builds for different CPUs so you need to build the package yourself:

NAN-s in the cost matrix lead to completely undefined result. It is the caller's responsibility to check them.

MIT Licensed,see LICENSE

The Tidelift Subscription provides access to a continuously curated stream of human-researched and maintainer-verified data on open source packages and their licenses, releases, vulnerabilities, and development practices.

See all contributors

Something wrong with this page? Make a suggestion

Export .ABOUT file for this package

Last synced: 2023-02-03 18:15:09 UTC

Login to resync this project

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

Linear Assignment Problem — A Javascript implementation of R. Jonker and A. Volgenant’s algorithm (LAPJV)

Folders and files

Repository files navigation, linear assignment problem — algorithm by r. jonker and a. volgenant.

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

Ported to javascript by Philippe Rivière, from the C++ implementation found at https://github.com/yongyanghz/LAPJV-algorithm-c

Added an epsilon to avoid infinite loops caused by rounding errors.

In the Linear Assignment Problem , you have n agents and n tasks, and need to assign one task to each agent, at minimal cost.

First, compute the cost matrix: how expensive it is to assign agent i (rows) to task j (columns).

The LAP-JV algorithm will give an optimal solution:

Here agent 0 is assigned to task 0, agent 1 to task 2, agent 2 to task 1, resulting in a total cost of 1 + 1 + 2 = 4 .

Cost callback

For performance and usability reasons, the lap function now accepts a cost callback cost(i,j) instead of a cost matrix:

The algorithm runs in O(n^2) . You can run it directly or as a javascript worker, as in the following example:

In the example above, we assign n points to a grid of n positions. costs[i][j] is the square distance between point i 's original coordinates and position j 's coordinates. The algorithm minimizes the total cost, i.e. the sum of square displacements.

Comments and patches at Fil/lap-jv .

• JavaScript 100.0%

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  

5246 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

Help Center Help Center

• Help Center
• Trial Software
• Product Updates
• Documentation

Jonker-Volgenant global nearest neighbor assignment algorithm

Description

[ assignments , unassignedrows , unassignedcolumns ] = assignjv( costmatrix , costofnonassignment ) returns a table of assignments of detections to tracks using the Jonker-Volgenant algorithm. The JV algorithm finds an optimal solution to the global nearest neighbor (GNN) assignment problem by finding the set of assignments that minimize the total cost of the assignments. The Jonker-Volgenant algorithm solves the GNN assignment in two phases: begin with the auction algorithm and end with the Dijkstra shortest path algorithm.

The cost of each potential assignment is contained in the cost matrix, costmatrix . Each matrix entry represents the cost of a possible assignments. Matrix rows represent tracks and columns represent detections. All possible assignments are represented in the cost matrix. The lower the cost, the more likely the assignment is to be made. Each track can be assigned to at most one detection and each detection can be assigned to at most one track. If the number of rows is greater than the number of columns, some tracks are unassigned. If the number of columns is greater than the number of rows, some detections are unassigned. You can set an entry of costmatrix to Inf to prohibit an assignment.

costofnonassignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every existing object is assigned.

The function returns a list of unassigned tracks, unassignedrows , and a list of unassigned detections, unassignedcolumns .

collapse all

Assign Detections to Tracks Using Jonker-Volgenant Algorithm

Use assignjv to assign three detections to two tracks.

Start with two predicted track locations in x-y coordinates.

Assume three detections are received. At least one detection will not be assigned.

Construct a cost matrix by defining the cost of assigning a detection to a track as the Euclidean distance between them. Set the cost of non-assignment to 0.2.

Use the Auction algorithm to assign detections to tracks.

Display the assignments.

Show that there are no unassigned tracks.

Display the unassigned detections.

Plot the detection to track assignments.

The track to detection assignments are:

Detection 1 is assigned to track 1.

Detection 2 is assigned to track 2.

Detection 3 is not assigned.

Input Arguments

Costmatrix — cost matrix real-valued m -by- n.

Cost matrix, specified as an M -by- N matrix. M is the number of tracks to be assigned and N is the number of detections to be assigned. Each entry in the cost matrix contains the cost of a track and detection assignment. The matrix may contain Inf entries to indicate that an assignment is prohibited. The cost matrix cannot be a sparse matrix.

Data Types: single | double

costofnonassignment — cost of non-assignment of tracks and detections scalar

Cost of non-assignment, specified as a scalar. The cost of non-assignment represents the cost of leaving tracks or detections unassigned. Higher values increase the likelihood that every object is assigned. The value cannot be set to Inf .

The costofnonassignment is half of the maximum cost that a successful assignment can have.

Output Arguments

Assignments — assignment of tracks to detections integer-valued l -by-2 matrix.

Assignment of detections to track, returned as an integer-valued L -by-2 matrix where L is the number of assignments. The first column of the matrix contains the assigned track indices and the second column contains the assigned detection indices.

Data Types: uint32

unassignedrows — Indices of unassigned tracks integer-valued P -by-1 column vector

Indices of unassigned tracks, returned as an integer-valued P -by-1 column vector.

unassignedcolumns — Indices of unassigned detections integer-valued Q -by-1 column vector

Indices of unassigned detections, returned as an integer-valued Q -by-1 column vector.

[1] Samuel S. Blackman and Popoli, R. Design and Analysis of Modern Tracking Systems . Artech House: Norwood, MA. 1999.

Extended Capabilities

C/c++ code generation generate c and c++ code using matlab® coder™., version history.

Introduced in R2018b

• assignauction | assignkbest | assignkbestsd | assignmunkres | assignsd | assignTOMHT | trackerTOMHT | trackerGNN

MATLAB Command

You clicked a link that corresponds to this MATLAB command:

Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.

Select a Web Site

Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .

• Switzerland (English)
• Switzerland (Deutsch)
• Switzerland (Français)
• 中国 (English)

You can also select a web site from the following list:

How to Get Best Site Performance

Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.

• América Latina (Español)
• Canada (English)
• United States (English)
• Belgium (English)
• Denmark (English)
• Deutschland (Deutsch)
• España (Español)
• Finland (English)
• France (Français)
• Ireland (English)
• Italia (Italiano)
• Luxembourg (English)
• Netherlands (English)
• Norway (English)
• Österreich (Deutsch)
• Portugal (English)
• Sweden (English)
• United Kingdom (English)

Asia Pacific

• Australia (English)
• India (English)
• New Zealand (English)

Contact your local office

lap05 0.5.1

pip install lap05 Copy PIP instructions

Released: Apr 22, 2022

Linear Assignment Problem solver (LAPJV/LAPMOD).

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: BSD (2-clause)

Maintainer: Tomas Kazmar

Classifiers

• Science/Research
• Microsoft :: Windows
• Python :: 2
• Python :: 2.7
• Python :: 3
• Python :: 3.7
• Python :: 3.8
• Python :: 3.9

Project description

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense (LAPJV) or sparse (LAPMOD) matrices.

Project details

Release history release notifications | rss feed.

Apr 22, 2022

Feb 8, 2022

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 22, 2022 Source

Hashes for lap05-0.5.1.tar.gz

• português (Brasil)

Supported by

Combinatorial Reinforcement Learning of Linear Assignment Problems

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.