Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Other Applied Mathematics
Characterizing Linearizable Qaps By The Level-1 Reformulation-Linearization Technique, Lucas Waddell, Warren Adams
Characterizing Linearizable Qaps By The Level-1 Reformulation-Linearization Technique, Lucas Waddell, Warren Adams
Faculty Journal Articles
The quadratic assignment problem (QAP) is an extremely challenging NP-hard combinatorial optimization program. Due to its difficulty, a research emphasis has been to identify special cases that are polynomially solvable. Included within this emphasis are instances which are linearizable; that is, which can be rewritten as a linear assignment problem having the property that the objective function value is preserved at all feasible solutions. Various known sufficient conditions for identifying linearizable instances have been explained in terms of the continuous relaxation of a weakened version of the level-1 reformulation-linearization-technique (RLT) form that does not enforce nonnegativity on a subset …