Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Engineering
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 …
Strengthening A Linear Reformulation Of The 0-1 Cubic Knapsack Problem Via Variable Reordering, Richard Forrester, Lucas Waddell
Strengthening A Linear Reformulation Of The 0-1 Cubic Knapsack Problem Via Variable Reordering, Richard Forrester, Lucas Waddell
Faculty Journal Articles
The 0-1 cubic knapsack problem (CKP), a generalization of the classical 0-1 quadratic knapsack problem, is an extremely challenging NP-hard combinatorial optimization problem. An effective exact solution strategy for the CKP is to reformulate the nonlinear problem into an equivalent linear form that can then be solved using a standard mixed-integer programming solver. We consider a classical linearization method and propose a variant of a more recent technique for linearizing 0-1 cubic programs applied to the CKP. Using a variable reordering strategy, we show how to improve the strength of the linear programming relaxation of our proposed reformulation, which ultimately …