Opened 5 years ago

Closed 5 years ago

#1856 closed enhancement (done)

Add GilmoreLawler lower bound for the QAP

Reported by: abeham Owned by: gkronber
Priority: medium Milestone: HeuristicLab 3.3.7
Component: Problems.QuadraticAssignment Version: 3.3.7
Keywords: Cc:

Description

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

Change History (8)

comment:1 Changed 5 years ago by abeham

  • Status changed from new to accepted

comment:2 Changed 5 years ago by abeham

r7877: Added Gilmore-Lawler lower bound

comment:3 Changed 5 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from accepted to reviewing

comment:4 Changed 5 years ago by gkronber

  • Owner changed from gkronber to abeham
  • Status changed from reviewing to assigned

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.

comment:5 Changed 5 years ago by 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.

comment:6 Changed 5 years ago by abeham

  • Owner changed from abeham to gkronber
  • Status changed from assigned to reviewing

comment:7 Changed 5 years ago by gkronber

  • Status changed from reviewing to readytorelease

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.

comment:8 Changed 5 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.6 to 3.3.7
Note: See TracTickets for help on using tickets.