Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis |
| |
Authors: | Michael J Brusco Hans-Friedrich Köhn Stephanie Stahl |
| |
Institution: | (1) Department of Marketing, College of Business, Florida State University, Tallahassee, FL 32306-1110, USA;(2) University of Missouri-Columbia, Columbia, MO, USA;(3) Tallahassee, FL, USA |
| |
Abstract: | Dynamic programming methods for matrix permutation problems in combinatorial data analysis can produce globally-optimal solutions
for matrices up to size 30×30, but are computationally infeasible for larger matrices because of enormous computer memory
requirements. Branch-and-bound methods also guarantee globally-optimal solutions, but computation time considerations generally
limit their applicability to matrix sizes no greater than 35×35. Accordingly, a variety of heuristic methods have been proposed
for larger matrices, including iterative quadratic assignment, tabu search, simulated annealing, and variable neighborhood
search. Although these heuristics can produce exceptional results, they are prone to converge to local optima where the permutation
is difficult to dislodge via traditional neighborhood moves (e.g., pairwise interchanges, object-block relocations, object-block
reversals, etc.). We show that a heuristic implementation of dynamic programming yields an efficient procedure for escaping
local optima. Specifically, we propose applying dynamic programming to reasonably-sized subsequences of consecutive objects
in the locally-optimal permutation, identified by simulated annealing, to further improve the value of the objective function.
Experimental results are provided for three classic matrix permutation problems in the combinatorial data analysis literature:
(a) maximizing a dominance index for an asymmetric proximity matrix; (b) least-squares unidimensional scaling of a symmetric
dissimilarity matrix; and (c) approximating an anti-Robinson structure for a symmetric dissimilarity matrix.
We are extremely grateful to the Associate Editor and two anonymous reviewers for helpful suggestions and corrections. |
| |
Keywords: | Combinatorial data analysis matrix permutation dynamic programming heuristics |
本文献已被 SpringerLink 等数据库收录! |
|