Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

How to use Jonker's LAP Linear Assigment Prolem code

Posted on 2006-11-04
6
Medium Priority
?
1,394 Views
Last Modified: 2008-01-09
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
0
Comment
Question by:Jose Parrot
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
6 Comments
 
LVL 27

Expert Comment

by:aburr
ID: 17873765
Have you tried looking at
"A Shortest Augmenting Path Algorithm for Dense and Sparse Linear  
    Assignment Problems," Computing 38, 325-340, 1987
?
0
 
LVL 18

Author Comment

by:Jose Parrot
ID: 17885816
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
0
 
LVL 27

Expert Comment

by:aburr
ID: 17886978
"Meanwhile I'm trying to understand it."
and if you, do you will be ahead of me.
0
 
LVL 18

Author Comment

by:Jose Parrot
ID: 18248302
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
0
 
LVL 1

Accepted Solution

by:
DarthMod earned 0 total points
ID: 18317224
PAQd, 500 points refunded.

DarthMod
CS Moderator
0

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever thought of installing a power system that generates solar electricity to power your house? Some may say yes, while others may tell me no. But have you noticed that people around you are now considering installing such systems in their …
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaac…

598 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question