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

Available for download on Friday, July 03, 2020

Share

COinS