Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis

Michael J. Brusco, Hans Friedrich Köhn, Stephanie Stahl

Research output: Contribution to journalArticle

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.

Original languageEnglish (US)
Pages (from-to)503-522
Number of pages20
JournalPsychometrika
Volume73
Issue number3
DOIs
StatePublished - Sep 1 2008
Externally publishedYes

Keywords

  • Combinatorial data analysis
  • Dynamic programming
  • Heuristics
  • Matrix permutation

ASJC Scopus subject areas

  • Psychology(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis'. Together they form a unique fingerprint.

  • Cite this