Date of Award
5-2015
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Mathematical Science
Committee Chair/Advisor
Warren P. Adams
Committee Member
Akshay S. Gupte
Committee Member
Matthew J. Saltzman
Committee Member
J. Cole Smith
Abstract
This research effort is concerned with identifying and characterizing families of polynomially solvable instances of the celebrated NP-hard quadratic assignment problem (qap). The approach is novel in that it uses polyhedral methods based on an equivalent mixed 0-1 linear reformulation of the problem. The continuous relaxation of this mixed 0-1 form yields a feasible region having extreme points that are both binary and fractional. The solvable instances of concern essentially possess objective function structures that ensure a binary extreme point must be optimal, so that the linear program solves the qap. The ultimate contribution of this work is the unification and subsumption of a variety of known solvable instances of the qap, and the development of a theoretical framework for identifying richer families of solvable instances. The qap was introduced over 50 years ago in the context of facility layout and location. The underlying mathematical structure, from which the problem draws its name, consists of the minimization of a quadratic function of binary variables over an assignment polytope. Since its inception, this structure has received considerable attention from various researchers, both practitioners and theoreticians alike, due to the diversity of practical applications and the resistance to exact solution procedures. Unfortunately, the combinatorial explosion of feasible solutions to the qap, in terms of the number of binary variables, creates a significant gap between the sizes of the motivating applications and the instances that can be solved by state-of-the-art solution algorithms. The most successful algorithms rely on linear forms of the qap to compute bounds within enumerative schemes. The inability to solve large qap instances has motivated researchers to seek special objective function structures that permit polynomial solvability. Various, seemingly unrelated, structures are found in the literature. This research shows that many such structures can be explained in terms of the linear reformulation which results from applying the level-1 reformulation-linearization technique (RLT) to the qap. In fact, the research shows that the level-1 RLT not only serves to explain many of these instances, but also allows for simplifications and/or generalizations. One important structure centers around instances deemed to be linearizable, where a qap instance is defined to be linearizazble if it can be equivalently rewritten as a linear assignment problem that preserves the objective function value at all feasible points. A contribution of this effort is that the constraint structure of a relaxed version of the continuous relaxation of the level-1 RLT form gives rise to a necessary and sufficient condition for an instance of the qap to be linearizable. Specifically, an instance of the qap is linearizable if and only if the given relaxed level-1 RLT form has a finite optimal solution. For all such cases, an optimal solution must occur at a binary extreme point. As a consequence, all linearizable qap instances are solvable via the level-1 RLT. The converse, however is not true, as the continuous relaxation of the level-1 RLT form can have a binary optimal solution when the qap is not linearizable. Thus, the linear program available from the level-1 RLT theoretically identifies a richer family of solvable instances. Notably, and as a consequence of this study, the level-1 RLT serves as a unifying entity in that it integrates the computation of linear programming-based bounds with the identification of polynomially solvable special cases, a relationship that was previously unnoticed.
Recommended Citation
Waddell, Lucas, "Linear Programming Methods for Identifying Solvable Cases of the Quadratic Assignment Problem" (2015). All Dissertations. 1535.
https://tigerprints.clemson.edu/all_dissertations/1535