Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis

Autor/inn/en	Brusco, Michael J.; Kohn, Hans-Friedrich; Stahl, Stephanie
Titel	Heuristic Implementation of Dynamic Programming for Matrix Permutation Problems in Combinatorial Data Analysis
Quelle	In: Psychometrika, 73 (2008) 3, S.503-522 (20 Seiten) PDF als Volltext Verfügbarkeit
Sprache	englisch
Dokumenttyp	gedruckt; online; Zeitschriftenaufsatz
ISSN	0033-3123
DOI	10.1007/s11336-007-9049-5
Schlagwörter	Heuristics; Programming; Data Analysis; Matrices; Computation + Suchen Sie Ihr Suchwort? Heuristik; Programmierung; Auswertung; Matrizenrechnung
Abstract	Dynamic programming methods for matrix permutation problems in combinatorial data analysis can produce globally-optimal solutions for matrices up to size 30x30, 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 35x35. 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. (As Provided).
Anmerkungen	Springer. 233 Spring Street, New York, NY 10013. Tel: 800-777-4643; Tel: 212-460-1500; Fax: 212-348-4505; e-mail: service-ny@springer.com; Web site: http://www.springerlink.com
Erfasst von	ERIC (Education Resources Information Center), Washington, DC
Update	2017/4/10