Optimal least-squares unidimensional scaling: Improved branch-and-bound procedures and comparison to dynamic programming

作     者：Brusco, MJ Stahl, S 

作者机构：Florida State Univ Coll Business Dept Marketing Tallahassee FL 32306 USA 

出 版 物：《PSYCHOMETRIKA》 (心理测量学)

年 卷 期：2005年第70卷第2期

页      面：253-270页

核心收录：

学科分类：0402[教育学-心理学(可授教育学、理学学位）] 04[教育学] 0701[理学-数学] 

主　　题：combinatorial data analysis least-squares unidimensional scaling branch-and-bound dynamic programming 

摘      要：There are two well-known methods for obtaining a guaranteed globally optimal solution to the problem of least-squares unidimensional scaling of a symmetric dissimilarity matrix: ( a) dynamic programming, and (b) branch-and-bound. Dynamic programming is generally more efficient than branch-and-bound, but the former is limited to matrices with approximately 26 or fewer objects because of computer memory limitations. We present some new branch-and-bound procedures that improve computational efficiency, and enable guaranteed globally optimal solutions to be obtained for matrices with up to 35 objects. Experimental tests were conducted to compare the relative performances of the new procedures, a previously published branch-and-bound algorithm, and a dynamic programming solution strategy. These experiments, which included both synthetic and empirical dissimilarity matrices, yielded the following findings: (a) the new branch-and-bound procedures were often drastically more efficient than the previously published branch-and-bound algorithm, (b) when computationally feasible, the dynamic programming approach was more efficient than each of the branch-and-bound procedures, and ( c) the new branch-and-bound procedures require minimal computer memory and can provide optimal solutions for matrices that are too large for dynamic programming implementation.