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

Fingerprint

Combinatorial Data Analysis
Permutation Matrix
Dynamic programming
Dynamic Programming
Heuristics
Taboo
Dissimilarity
Simulated Annealing
Least-Squares Analysis
Permutation
Simulated annealing
Quadratic Assignment
Optimal Solution
Branch and Bound Method
Variable Neighborhood Search
Tabu Search
Branch and bound method
Heuristic Method
Reversal
Subsequence

Keywords

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

ASJC Scopus subject areas

  • Psychology(all)
  • Applied Mathematics

Cite this

Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis. / Brusco, Michael J.; Köhn, Hans Friedrich; Stahl, Stephanie.

In: Psychometrika, Vol. 73, No. 3, 01.09.2008, p. 503-522.

Research output: Contribution to journalArticle

@article{778a59cb5b51408ea8ea8adb8b157c66,
title = "Heuristic implementation of dynamic programming for matrix permutation problems in combinatorial data analysis",
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.",
keywords = "Combinatorial data analysis, Dynamic programming, Heuristics, Matrix permutation",
author = "Brusco, {Michael J.} and K{\"o}hn, {Hans Friedrich} and Stephanie Stahl",
year = "2008",
month = "9",
day = "1",
doi = "10.1007/s11336-007-9049-5",
language = "English (US)",
volume = "73",
pages = "503--522",
journal = "Psychometrika",
issn = "0033-3123",
publisher = "Springer New York",
number = "3",

}

TY - JOUR

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

AU - Brusco, Michael J.

AU - Köhn, Hans Friedrich

AU - Stahl, Stephanie

PY - 2008/9/1

Y1 - 2008/9/1

N2 - 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.

AB - 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.

KW - Combinatorial data analysis

KW - Dynamic programming

KW - Heuristics

KW - Matrix permutation

UR - http://www.scopus.com/inward/record.url?scp=46749128383&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46749128383&partnerID=8YFLogxK

U2 - 10.1007/s11336-007-9049-5

DO - 10.1007/s11336-007-9049-5

M3 - Article

AN - SCOPUS:46749128383

VL - 73

SP - 503

EP - 522

JO - Psychometrika

JF - Psychometrika

SN - 0033-3123

IS - 3

ER -