Linear assignment problems, part II

In a previous post I talked a bit about the linear assignment problem:  finding the minimum cost matching in a bipartite graph.  In my next post I will give a simple self-contained C# program for solving LAP based on some Fortran code from my colleague Rainer Burkard.  First a few notes and disclaimers!

The input to the code is a matrix which represents the adjacency matrix of the graph.  In my application (solving quadratic assignment problems) I am concerned with input matrices that are relatively small and dense.   The code is a port of Fortran code by Burkard and Ulrich Derigs:  Assignment and matching problems: Solution methods with Fortran programs, volume 184 of Lecture Notes in Economics and Mathematical Systems.  Springer, Berlin, 1980.  The original code is available on the QAPLIB site.  Rainer has given me permission to post this code, although if you look at the terms on the original you will see that it is freely distributable.  This code is offered under the same conditions and I make no claims about its correctness, value, etc.  But it works okay for me.

My port is relatively “conservative” in that I have tried to retain the original structure and flow as much as possible because I don’t want to introduce any bugs.  I want to keep the implementation clean, so like many numerical optimization codes there isn’t much input validation.  I have chosen to use arrays rather than trying to encapsulate the input and output into matrix and vector classes.  I kept it simple so you can adapt it to your needs.

Lastly, I wanted to mention that this is not the most efficient LAP solver available.  At the time I wrote my thesis the fastest code over the domain I was working on was the code of Jonker and Volgenant, which is available on this site.  I notice that the code is used by others as well, see here and here.  This code is really quite slick and I had a great experience working with it all those years ago.  It’s not hard to port it over to C#, so go for it!


Author: natebrix

Follow me on twitter at @natebrix.

One thought on “Linear assignment problems, part II”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s