A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem

摘要

We apply the level-3 reformulation-linearization technique (RLT3) to the quadratic assignment problem (QAP). We then present our experience in calculating lower bounds using an essentially new algorithm based on this RLT3 formulation. Our method is not guaranteed to calculate the RLT3 lower bound exactly, but it approximates this lower bound very closely and reaches it in some instances. For Nugent problem instances up to size 24, our RLT3-based lower bound calculation solves these problem instances exactly or serves to verify the optimal value. Calculating lower bounds for problem sizes larger than size 27 still presents a challenge because of the large amount of memory needed to implement the RLT3 formulation. Our presentation emphasizes the steps taken to significantly conserve memory by using the numerous problem symmetries in the RLT3 formulation of the QAP. We implemented this RLT3-based bound calculation in a branch-and-bound algorithm. Experimental results project significant runtime improvement over all other published QAP branch-and-bound solvers.