Optimal Least-Squares Unidimensional Scaling: Improved Branch-and-Bound Procedures and Comparison to 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.The authors gratefully acknowledge the helpful comments of three anonymous reviewers and the Editor. We especially thank Larry Hubert and one of the reviewers for providing us with the MATLAB files for optimal and heuristic least-squares unidimensional scaling methods.This revised article was published online in June 2005 with all corrections incorporated.     

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

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.     

Graph-theoretic representations for proximity matrices through strongly-anti-Robinson or circular strongly-anti-Robinson matrices

There are various optimization strategies for approximating, through the minimization of a least-squares loss function, a given symmetric proximity matrix by a sum of matrices each subject to some collection of order constraints on its entries. We extend these approaches to include components in the approximating sum that satisfy what are called the strongly-anti-Robinson (SAR) or circular strongly-anti-Robinson (CSAR) restrictions. A matrix that is SAR or CSAR is representable by a particular graph-theoretic structure, where each matrix entry is reproducible from certain minimum path lengths in the graph. One published proximity matrix is used extensively to illustrate the types of approximation that ensue when the SAR or CSAR constraints are imposed.The authors are indebted to Boris Mirkin who first noted in a personal communication to one of us (LH, April 22, 1996) that the optimization method for fitting anti-Robinson matrices in Hubert and Arabie (1994) should be extendable to the fitting of strongly anti-Robinson matrices as well.     

ConPar: a method for identifying groups of concordant subject proximity matrices for subsequent multidimensional scaling analyses

A common representation of data within the context of multidimensional scaling (MDS) is a collection of symmetric proximity (similarity or dissimilarity) matrices for each of M subjects. There are a number of possible alternatives for analyzing these data, which include: (a) conducting an MDS analysis on a single matrix obtained by pooling (averaging) the M subject matrices, (b) fitting a separate MDS structure for each of the M matrices, or (c) employing an individual differences MDS model. We discuss each of these approaches, and subsequently propose a straightforward new method (CONcordance PARtitioning—ConPar), which can be used to identify groups of individual-subject matrices with concordant proximity structures. This method collapses the three-way data into a subject×subject dissimilarity matrix, which is subsequently clustered using a branch-and-bound algorithm that minimizes partition diameter. Extensive Monte Carlo testing revealed that, when compared to K-means clustering of the proximity data, ConPar generally provided better recovery of the true subject cluster memberships. A demonstration using empirical three-way data is also provided to illustrate the efficacy of the proposed method.     

An enhanced branch‐and‐bound algorithm for a partitioning problem

This paper focuses on the problem of developing a partition of n objects based on the information in a symmetric, non‐negative dissimilarity matrix. The goal is to partition the objects into a set of non‐overlapping subsets with the objective of minimizing the sum of the within‐subset dissimilarities. Optimal solutions to this problem can be obtained using dynamic programming, branch‐and‐bound and other mathematical programming methods. An improved branch‐and‐bound algorithm is shown to be particularly efficient. The improvements include better upper bounds that are obtained via a fast exchange algorithm and, more importantly, sharper lower bounds obtained through sequential solution of submatrices. A modified version of the branch‐and‐bound algorithm for minimizing the diameter of a partition is also presented. Computational results for both synthetic and empirical dissimilarity matrices reveal the effectiveness of the branch‐and‐bound methodology.     

Identifying a Reordering of Rows and Columns for Multiple Proximity Matrices Using Multiobjective Programming

This paper is concerned with a problem where K (n×n) proximity matrices are available for a set of n objects. The goal is to identify a single permutation of the n objects that provides an adequate structural fit, as measured by an appropriate index, for each of the K matrices. A multiobjective programming approach for this problem, which seeks to optimize a weighted function of the K indices, is proposed, and illustrative examples are provided using a set of proximity matrices from the psychological literature. These examples show that, by solving the multiobjective programming model under different weighting schemes, the quantitative analyst can uncover information about the relationships among the matrices and often identify one or more permutations that provide good to excellent index values for all matrices.     

An algorithm for extracting maximum cardinality subsets with perfect dominance or anti‐Robinson structures

A common criterion for seriation of asymmetric matrices is the maximization of the dominance index, which sums the elements above the main diagonal of a reordered matrix. Similarly, a popular seriation criterion for symmetric matrices is the maximization of an anti‐Robinson gradient index, which is associated with the patterning of elements in the rows and columns of a reordered matrix. Although perfect dominance and perfect anti‐Robinson structure are rarely achievable for empirical matrices, we can often identify a sizable subset of objects for which a perfect structure is realized. We present and demonstrate an algorithm for obtaining a maximum cardinality (i.e. the largest number of objects) subset of objects such that the seriation of the proximity matrix corresponding to the subset will have perfect structure. MATLAB implementations of the algorithm are available for dominance, anti‐Robinson and strongly anti‐Robinson structures.     

Integer programs for one- and two-mode blockmodeling based on prespecified image matrices for structural and regular equivalence

Establishing blockmodels for one- and two-mode binary network matrices has typically been accomplished using multiple restarts of heuristic algorithms that minimize functions of inconsistency with an ideal block structure. Although these algorithms likely yield exceptional performance, they are not assured to provide blockmodels that optimize the functional indices. In this paper, we present integer programming models that, for a prespecified image matrix, can produce guaranteed optimal solutions for matrices of nontrivial size. Accordingly, analysts performing a confirmatory analysis of a prespecified blockmodel structure can apply our models directly to obtain an optimal solution. In exploratory cases where a blockmodel structure is not prespecified, we recommend a two-stage procedure, where a heuristic method is first used to identify an image matrix and the integer program is subsequently formulated and solved to identify the optimal solution for that image matrix. Although best suited for ideal block structures associated with structural equivalence, the integer programming models have the flexibility to accommodate functional indices pertaining to regular equivalence. Computational results are reported for a variety of one- and two-mode matrices from the blockmodeling literature.     

Divergence Behaviour of the Successive Geometric Mean Method of Pairwise Comparison Matrix Generation for a Multiple Stage,Multiple Objective Optimization Problem

This paper focuses on the divergence behaviour of the successive geometric mean (SGM) method used to generate pairwise comparison matrices while solving a multiple stage, multiple objective (MSMO) optimization problem. The SGM method can be used in the matrix generation phase of our three‐phase methodology to obtain pairwise comparison matrix at each stage of an MSMO optimization problem, which can be subsequently used to obtain the weight vector at the corresponding stage. The weight vectors across the stages can be used to convert an MSMO problem into a multiple stage, single objective (MSSO) problem, which can be solved using dynamic programming‐based approaches. To obtain a practical set of non‐dominated solutions (also referred to as Pareto optimal solutions) to the MSMO optimization problem, it is important to use a solution approach that has the potential to allow for a better exploration of the Pareto optimal solution space. To accomplish a more exhaustive exploration of the Pareto optimal solution space, the weight vectors that are used to scalarize the MSMO optimization problem into its corresponding MSSO optimization problem should vary across the stages. Distinct weight vectors across the stages are tied directly with distinct pairwise comparison matrices across the stages. A pairwise comparison matrix generation method is said to diverge if it can generate distinct pairwise comparison matrices across the stages of an MSMO optimization problem. In this paper, we demonstrate the SGM method's divergence behaviour when the three‐phase methodology is used in conjunction with an augmented high‐dimensional, continuous‐state stochastic dynamic programming method to solve a large‐scale MSMO optimization problem. Copyright © 2013 John Wiley & Sons, Ltd.     

Compact integer-programming models for extracting subsets of stimuli from confusion matrices

This paper presents an integer linear programming formulation for the problem of extracting a subset of stimuli from a confusion matrix. The objective is to select stimuli such that total confusion among the stimuli is minimized for a particular subset size. This formulation provides a drastic reduction in the number of variables and constraints relative to a previously proposed formulation for the same problem. An extension of the formulation is provided for a biobjective problem that considers both confusion and recognition in the objective function. Demonstrations using an empirical interletter confusion matrix from the psychological literature revealed that a commercial branch-and-bound integer programming code was always able to identify optimal solutions for both the single-objective and biobjective formulations within a matter of seconds. A further extension and demonstration of the model is provided for the extraction of multiple subsets of stimuli, wherein the objectives are to maximize similarity within subsets and minimize similarity between subsets.     

A Repetitive Branch-and-Bound Procedure for Minimum Within-Cluster Sums of Squares Partitioning

Minimization of the within-cluster sums of squares (WCSS) is one of the most important optimization criteria in cluster analysis. Although cluster analysis modules in commercial software packages typically use heuristic methods for this criterion, optimal approaches can be computationally feasible for problems of modest size. This paper presents a new branch-and-bound algorithm for minimizing WCSS. Algorithmic enhancements include an effective reordering of objects and a repetitive solution approach that precludes the need for splitting the data set, while maintaining strong bounds throughout the solution process. The new algorithm provided optimal solutions for problems with up to 240 objects and eight well-separated clusters. Poorly separated problems with no inherent cluster structure were optimally solved for up to 60 objects and six clusters. The repetitive branch-and-bound algorithm was also successfully applied to three empirical data sets from the classification literature.     

The approximation of two-mode proximity matrices by sums of order-constrained matrices

A least-squares strategy is proposed for representing a two-mode proximity matrix as an approximate sum of a small number of matrices that satisfy certain simple order constraints on their entries. The primary class of constraints considered define Q-forms (or anti-Q-forms) for a two-mode matrix, where after suitable and separate row and column reorderings, the entries within each row and within each column are nondecreasing (or nonincreasing) to a maximum (or minimum) and thereafter nonincreasing (or nondecreasing). Several other types of order constraints are also mentioned to show how alternative structures can be considered using the same computational strategy.     

Matrix reorganization and dynamic programming: Applications to paired comparisons and unidimensional seriation

A recursive dynamic programming strategy is discussed for optimally reorganizing the rows and simultaneously the columns of ann ×n proximity matrix when the objective function measuring the adequacy of a reorganization has a fairly simple additive structure. A number of possible objective functions are mentioned along with several numerical examples using Thurstone's paired comparison data on the relative seriousness of crime. Finally, the optimization tasks we propose to attack with dynamic programming are placed in a broader theoretical context of what is typically referred to as the quadratic assignment problem and its extension to cubic assignment.Partial support for this research was provided by NIJ Grant 80-IJ-CX-0061.     

A heuristic method for the comparison of related structures

By extending a technique for testing the difference between two dependent correlations developed by Wolfe, a strategy is proposed in a more general matrix context for evaluating a variety of data analysis schemes that are supposed to clarify the structure underlying a set of proximity measures. In the applications considered, a data analysis scheme is assumed to reconstruct in matrix form the given data set (represented as a proximity matrix) based on some specific model or procedure. Thus, an evaluation of the adequacy of reconstruction can be developed by comparing matrices, one containing the original proximities and the second containing the reconstructed values. Possible applications in multidimensional scaling, clustering, and related contexts are emphasized using four broad categories: (a) Given two different reconstructions based on a single data set, does either represent the data significantly better than the other? (b) Given two reconstructions based on a single data set using two different procedures (or possibly, two distinct data sets and a common method), is either reconstruction significantly closer to a particular theoretical structure that is assumed to underlie the data (where the latter is also represented in matrix form)? (c) Given two theoretical structures and one reconstruction based on a single data set, does either represent the reconstruction better than the other? (d) Given a single reconstruction based on one data set, is the information present in the data accounted for satisfactorily by the reconstruction? In all cases, these tasks can be approached by a nonparametric procedure that assesses the similarity in pattern between two appropriately defined matrices. The latter are obtained from the original data, the reconstructions, and/or the theoretical structures. Finally, two numerical examples are given to illustrate the more general discussion.     

Techniques for rotating two or more loading matrices to optimal agreement and simple structure: A comparison and some technical details

Matrices of factor loadings are often rotated to simple structure. When more than one loading matrix is available for the same variables, the loading matrices can be compared after rotating them all (separately) to simple structure. An alternative procedure is to rotate them to optimal agreement, and then compare them. In the present paper techniques are described that combine these two procedures. Specifically, five techniques that combine the ideals of rotation to optimal agreement and rotation to simple structure are compared on the basis of contrived and empirical data. For the contrived data, it is assessed to what extent the rotations recover the underlying common structure. For both the contrived and the empirical data it is studied to what extent the techniques give well matching rotated matrices, to what extent these have a simple structure, and to what extent the most prominent parts of the different loading matrices agree. It was found that the simple procedure of combining a Generalized Procrustes Analysis (GPA) with Varimax on the mean of the matched loading matrices performs very well on all criteria, and, for most purposes, offers an attractive compromise of rotation to agreement and simple structure. In addition to this comparison, some technical improvements are proposed for Bloxom's rotation to simple structure and maximum similarity.This research has been made possible by a fellowship from the Royal Netherlands Academy of Arts and Sciences to the author. The author is obliged to René van der Heijden for assistance in programming the procedures in the simulation study reported in this paper, and to Jos ten Berge, three anonymous reviewers and an associate editor for helpful comments on an earlier version of this paper.     

A variable neighborhood search method for generalized blockmodeling of two-mode binary matrices

The clustering of two-mode proximity matrices is a challenging combinatorial optimization problem that has important applications in the quantitative social sciences. We focus on one particular type of problem related to the clustering of a two-mode binary matrix, which is relevant to the establishment of generalized blockmodels for social networks. In this context, clusters for the rows of the two-mode matrix intersect with clusters of the columns to form blocks, which should ideally be either complete (all 1s) or null (all 0s). A new procedure based on variable neighborhood search is presented and compared to an existing two-mode K-means clustering algorithm. The new procedure generally provided slightly greater explained variation; however, both methods yielded exceptional recovery of cluster structure.     

Optimal Partitioning of a Data Set Based on the p-Median Model

Although the K-means algorithm for minimizing the within-cluster sums of squared deviations from cluster centroids is perhaps the most common method for applied cluster analyses, a variety of other criteria are available. The p-median model is an especially well-studied clustering problem that requires the selection of p objects to serve as cluster centers. The objective is to choose the cluster centers such that the sum of the Euclidean distances (or some other dissimilarity measure) of objects assigned to each center is minimized. Using 12 data sets from the literature, we demonstrate that a three-stage procedure consisting of a greedy heuristic, Lagrangian relaxation, and a branch-and-bound algorithm can produce globally optimal solutions for p-median problems of nontrivial size (several hundred objects, five or more variables, and up to 10 clusters). We also report the results of an application of the p-median model to an empirical data set from the telecommunications industry.     

Multiobjective Blockmodeling for Social Network Analysis

To date, most methods for direct blockmodeling of social network data have focused on the optimization of a single objective function. However, there are a variety of social network applications where it is advantageous to consider two or more objectives simultaneously. These applications can broadly be placed into two categories: (1) simultaneous optimization of multiple criteria for fitting a blockmodel based on a single network matrix and (2) simultaneous optimization of multiple criteria for fitting a blockmodel based on two or more network matrices, where the matrices being fit can take the form of multiple indicators for an underlying relationship, or multiple matrices for a set of objects measured at two or more different points in time. A multiobjective tabu search procedure is proposed for estimating the set of Pareto efficient blockmodels. This procedure is used in three examples that demonstrate possible applications of the multiobjective blockmodeling paradigm.     

认知诊断中的Q矩阵及其作用

Q矩阵作为连接认知和测量的桥梁,在认知诊断中起重要作用。本文梳理了应用Q矩阵解决认知诊断相关问题的理论与方法。首先整理Q矩阵的相关概念、算法、性质及其在认知诊断中的作用;并根据Q矩阵可计算理论构念效度、可以构成格等,指出Q矩阵是特殊的关联矩阵;接着介绍Q矩阵理论研究方面的几个近期发展;并对Q矩阵未来的应用研究作出展望。期望本文能为测量工作者更灵活地利用Q矩阵提供参考和帮助。     

Joint Procrustes Analysis for Simultaneous Nonsingular Transformation of Component Score and Loading Matrices

In component analysis solutions, post-multiplying a component score matrix by a nonsingular matrix can be compensated by applying its inverse to the corresponding loading matrix. To eliminate this indeterminacy on nonsingular transformation, we propose Joint Procrustes Analysis (JPA) in which component score and loading matrices are simultaneously transformed so that the former matrix matches a target score matrix and the latter matches a target loading matrix. The loss function of JPA is a function of the nonsingular transformation matrix and its inverse, and is difficult to minimize straightforwardly. To deal with this difficulty, we reparameterize those matrices by their singular value decomposition, which reduces the minimization to alternately solving quartic equations and performing the existing multivariate procedures. This algorithm is assessed in a simulation study. We further extend JPA for cases where targets are linear functions of unknown parameters. We also discuss how the application of JPA can be extended in different fields.