Date of Degree
Access restricted until 07/03/2020
PhD (Doctor of Philosophy)
Applied Mathematical and Computational Sciences
Stewart, David E
First Committee Member
Second Committee Member
Third Committee Member
Fourth Committee Member
The quadratic assignment problem (QAP) is known to be one of the most computationally difficult combinatorial problems. Optimally solvable instances of the QAP remain of size n ≤ 40 with heuristics used to solve instances in the range 40 ≤ n ≤ 256. In this thesis we develop a local optimization algorithm called GradSwaps (GS). GS uses the first-order Taylor approximation (FOA) to efficiently determine improving swaps in the solution. We use GS to locally optimize instances of the QAP of size 1000 ≤ n ≤ 70000 where the data matrices are given in factored form, enabling efficient computations. We give theoretical background and justification for using the FOA and bound the error inherent in the approximation. A strategy for extending GS to larger scale QAPs using blocks of indices is described in detail.
Three novel large-scale applications of the QAP are developed. First, a strategy for data visualization using an extreme learning machine (ELM) where the quality of the visualization is measured in the original data space instead of the projected space. Second, a version of the traveling salesperson problem (TSP) with the squared Euclidean distance metric; this distance metric allows the factorization of the data matrix, a key component for using GS. Third, a method for generating random data with designated distribution and correlation to an accuracy surpassing traditional techniques.
Heuristics, Linear Approximation, Local Optimization, Quadratic Assignment
ix, 128 pages
Includes bibliographical references (pages 117-128).
Copyright © 2018 Cole Stiegler
Stiegler, Cole. "Efficient local optimization for low-rank large-scale instances of the quadratic assignment problem." PhD (Doctor of Philosophy) thesis, University of Iowa, 2018.