Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
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 …
An Lp-Based Characterization Of Solvable Qap Instances With Chess-Board And Graded Structures, Lucas Waddell, Jerry Phillips, Tianzhu Liu, Swarup Dhar
An Lp-Based Characterization Of Solvable Qap Instances With Chess-Board And Graded Structures, Lucas Waddell, Jerry Phillips, Tianzhu Liu, Swarup Dhar
Faculty Journal Articles
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 efficiently. Previous work has shown that certain such structures can be explained in terms of a mixed 0-1 linear reformulation of the QAP 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 …