Add GilmoreLawler lower bound for the QAP

[abeham]

This lower bound is not as good as others, but rather quick to compute and thus widely used.

[abeham]

r7877: Added Gilmore-Lawler lower bound

[gkronber]

r7877: I think there is a bug in the loop in lines 35 and 36. I saw the fortran source uses vector indices starting at 1. When you iterate over k it seems you want to add all costs multiplying the first distance with the last weight and vice versa. However, using k< n-1 and n - 2 - k you omit one pair! (when you use indices starting at 0) Please check the code and then assign the ticket again to me for review.

[abeham]

No that's okay, the last column contains the diagonal elements which are added to the sum after the innermost loop (line 37). I made this more obvious in r8092 and also added a unit test that checks with some pre-computed samples (I didn't want to break anything with the changes).

As you probably already understood the idea here is to transform the weights and distance matrix into a single cost matrix that would underestimate the true costs of the quadratic assignment. For this purpose the cost matrix elements c_ij denote the cost of inserting facility i in location j. In the quadratic case this cost highly depends on the other assignments, so here the cost is underestimating the quadratic case. It is calculated as the sum of the products involving the maximum weight of facility i with the minimum distance that location j has to other facilities (continuing by taking the 2nd-maximum weight with the 2nd-closest location). Finally, there's the linear cost of inserting facility i in location j which is the product of both diagonals.

The optimal quality of the resulting linear assignment problem is considered to be a lower bound to the quadratic assignment problem.

[gkronber]

Ok, thanks for the explanation. You are right, I missed that the last row contains the diagonal after SortEachRowExceptDiagonal. It's good to have the unit test to assure that the calculator works correctly.