Title
Efficient local optimization for low-rank large-scale instances of the quadratic assignment problem
DOI
10.17077/etd.j823svqv
Document Type
Dissertation
Date of Degree
Spring 2018
Access Restrictions
Access restricted until 07/03/2020
Degree Name
PhD (Doctor of Philosophy)
Degree In
Applied Mathematical and Computational Sciences
First Advisor
Stewart, David E.
First Committee Member
Campbell, Ann
Second Committee Member
Jorgensen, Palle
Third Committee Member
Lendasse, Amaury
Fourth Committee Member
Ohlmann, Jeffrey
Abstract
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.
Keywords
Heuristics, Linear Approximation, Local Optimization, Quadratic Assignment
Pages
ix, 128 pages
Bibliography
Includes bibliographical references (pages 117-128).
Copyright
Copyright © 2018 Cole Stiegler
Recommended Citation
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.
https://doi.org/10.17077/etd.j823svqv