An LP-based Characterizations Of Solvable Cases Of the Quadratic Assignment Problem
Author:
Tianzhu Liu ’22Co-Authors:
Swarup DharFaculty Mentor(s):
Lucas Waddell, MathematicsFunding Source:
Program for Undergraduate ResearchAbstract
The quadratic assignment problem (QAP) is perhaps the most widely studied nonlinear combinatorial optimization problem. It has many applications in various fields, yet has proven to be extremely difficult to solve. This difficulty has motivated researchers to identify special objective function structures that permit an optimal solution to be found in an efficient manner. Previous work has shown that certain such structures can be explained in terms of the continuous relaxation of a mixed 0-1 linear reformulation of the problem known as the level-1 reformulation-linearization-technique (RLT) form. Specifically, the objective function structures were shown to ensure that a binary optimal extreme point solution exists to the continuous relaxation. This paper extends that work by considering known solvable cases in which the objective function coefficients have special chess-board and graded structures, and similarly characterizing them in terms of the level-1 RLT form. As part of this characterization, we develop a new relaxed version of the level-1 RLT form, the structure of which can be readily exploited to study the special instances under consideration.