For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the algorithm that is commonly used is Branch and Bound. I understand the basics of the problem and I see the need of a lower bound to compute the sollution. I came up with a trivial bound example but our teacher told us lower bounds were no trivial matter and we should do some research. After a while we've found out that the Gilmore-Lawler bound is a good one to solve our problem (or at least good enough for learning purposes).

Although I have read a couple of papers I can't get the grasp of it. The idea seems to be to convert the QAP into an LAP combining the two matrices of the original problem. I've got completely lost after that. How is the number I'm supposed to find as the lower bound calculated?

Also, I'm aware that the lower bound has to be calculated for partial solutions, but how do I do that? The lower bound, as I understood, it's calculated from the program's matrices, which are a parameter for the branch and bound algorithm and are fixed from the beginning aren't they? I'd also need an explanation for that.

  • $\begingroup$ Have you tried working some small examples through by hand to try to get some intuition for what's going on? $\endgroup$
    – D.W.
    Mar 28 '14 at 4:35
  • $\begingroup$ I've done it for the branch and bound procedure and I understand that byt when it comes to apply a nontrivial lower bound (Gilmore-Lawler in my case) I don't know where to begin. Although I've been reading more about it and now my doubts have become more precise than before. I will try to rephrase my questions. $\endgroup$
    – Setzer22
    Mar 28 '14 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.