How to use Jonker's LAP Linear Assigment Prolem code
Hello,
I'd appreciate any help on how to use Jonker's LAP, something like an "user guide" or some samples.
The only info I have is inside the code itself:
/*
* lap.cpp
version 1.0 - 4 September 1996
author: Roy Jonker @ MagicLogic Optimization Inc.
e-mail: roy_jonker@magiclogic.com
Code for Linear Assignment Problem, according to
"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear
Assignment Problems," Computing 38, 325-340, 1987
by
R. Jonker and A. Volgenant, University of Amsterdam.
*/
Unfortunatelly there is no information about LAP at those organizations' sites anymore.
I'd like to apply LAP in place of the simple DFS I used in my branch-and-bound CVRP solver.
Please note this is not homework. I have already done my assignments at my graduate course, when I used DFS and a LP version with the huge SYMPHONY package in similar problems. What I'm like now is a light solution by using public domain software.
Thanks in advance,
Jose
I'd appreciate any help on how to use Jonker's LAP, something like an "user guide" or some samples.
The only info I have is inside the code itself:
/*
* lap.cpp
version 1.0 - 4 September 1996
author: Roy Jonker @ MagicLogic Optimization Inc.
e-mail: roy_jonker@magiclogic.com
Code for Linear Assignment Problem, according to
"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear
Assignment Problems," Computing 38, 325-340, 1987
by
R. Jonker and A. Volgenant, University of Amsterdam.
*/
Unfortunatelly there is no information about LAP at those organizations' sites anymore.
I'd like to apply LAP in place of the simple DFS I used in my branch-and-bound CVRP solver.
Please note this is not homework. I have already done my assignments at my graduate course, when I used DFS and a LP version with the huge SYMPHONY package in similar problems. What I'm like now is a light solution by using public domain software.
Thanks in advance,
Jose
ASKER
Of course. Not only read it but I've paid US$ 30 for this paper a few weeks ago. Although the algorithm is presented, there is no samples. I had used this code in C and the results were very far to the expected, obviously because I'm using it wrongly. As this LAP code is widely cited in many papers (I have read a number of them) this reinforces that I didn't understood the original paper. Probably it is a little but important detail I wasn't able to see...
I had the hope of one of the experts around knew this program and have used it.
Meanwhile I'm trying to understand it.
Jose
I had the hope of one of the experts around knew this program and have used it.
Meanwhile I'm trying to understand it.
Jose
"Meanwhile I'm trying to understand it."
and if you, do you will be ahead of me.
and if you, do you will be ahead of me.
ASKER
Hi,
I have discovered that the C code I have has a bug.
Then I have ported the Pascal code, from the cited paper, to C and compared it with the C code I had and notice some significant differences. The problem is that the C code was distributed by a graduation teacher as an additional resource for solving the TSP, and, was supposed to be correct. Oh, it make me spent a time!
So what I can do is to advice: if you find elsewhere codes named lapjv.c or lap.c or lapjv.pas around, probably they are wrong. The only correct solver for the Linear Assignment Problem, by R. Jonker and A. Volgenant, is the one described in such paper. Despite the age (the paper is 10 years old), it is very useful and fast. Really good algorithm and code.
As I didn't received answers, I'll ask for the deletion of the question.
Anyway, thanks, aburr, for your attention.
Jose
I have discovered that the C code I have has a bug.
Then I have ported the Pascal code, from the cited paper, to C and compared it with the C code I had and notice some significant differences. The problem is that the C code was distributed by a graduation teacher as an additional resource for solving the TSP, and, was supposed to be correct. Oh, it make me spent a time!
So what I can do is to advice: if you find elsewhere codes named lapjv.c or lap.c or lapjv.pas around, probably they are wrong. The only correct solver for the Linear Assignment Problem, by R. Jonker and A. Volgenant, is the one described in such paper. Despite the age (the paper is 10 years old), it is very useful and fast. Really good algorithm and code.
As I didn't received answers, I'll ask for the deletion of the question.
Anyway, thanks, aburr, for your attention.
Jose
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear
Assignment Problems," Computing 38, 325-340, 1987
?