1
$\begingroup$

I'm stuck with trying to implement the Gilmore-Lawler bound procedure for the quadratic assignment problem (QAP). That is, a bound one can use with a branch and bound algorithm to solve the QAP. I'm gonna explain what I've understood about it and I'd like anyone who knows on the topic correct me, or tell me if I'm right.

As far as I know it's an optimistic (better than any of the possible outcomes) for a given partial solution for the QAP. I'll put it in terms of facilities and locations (which is what I've seen used mostly).

Let's say at a given moment we've assigned m of the n facilities to m locations. From the solution space of the m-n locations that need to be assigned, one can calculate an optimistic bound which corresponds to the sum of three terms.

The first term is the cost of what we already have assigned, so we just calculate the cost for the fist m terms as if the problem was just a smaller one.

For the next two we'll consider each of the pairs of unassigned facilities and unassigned locations, so more formally, each pair (f,l) with f and l in {m-n..n}.

For each pair (f,l) we'll determine the contribution of making that assignment to the total cost of the problem. I've been told that doing this for all pairs of (f,l) corresponds to an (n-m)x(n-m) matrix M1 = (m_fl) with m_fl being the cost (objective function) of a m+1 QAP, with the same distance and flow matrices and m assignments and the m+1th asignment being (f,l).

Also, for each pair (f,l) we'll determine the cost of making that assignment in regards to all the unassigned facilities and locations. We'll define another matrix M2 = m2_fl. To calculate m2_fl let's define two vectors vd and vf, the first it's the vector that corresponds to the distance from l to all the other unassigned locations. The second it's the vector that corresponds to the flow from f to all the other unassigned facilities. Now, m2_fl it's the result of the minimal scalar product of vd and vf —That being the scalar product of vd and vf sorted in opposed orders—.

Now, let's consider the matrix M = M1+M2, and objective value of the linear assignment problem associated to M, which we'll denote by c. Knowing that we can say that the Gilmore-Lawler lower bound to that particular partial sollution is the first term added with c.

Now, I want to know if I am right. It makes sense to me, I've ran some examples by paper and they make sense to me. But papers on this are too complicated, or just trying to improve this bound and not bothering on explaining it to a begginer. So it's really difficult to just know if I'm doing the right thing. I also tried to get the first article written by Gilmore (also the Lawler's one) which would tell the original method but none of them both seems to be free to read.

$\endgroup$
  • $\begingroup$ what is the gilmore-lawler bound ? $\endgroup$ – Suresh Venkat Apr 25 '14 at 20:41
  • $\begingroup$ It's the most commonly used bound for the quadratic assignment problem. A bound for the branch and bound algorithm, of course, which I tried to explain as well as I could throughout my whole question to see if I got it right. I'm going to edit it to contextualize a little bit more. $\endgroup$ – Setzer22 Apr 25 '14 at 20: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.