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.     

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.     

Statistical inference of minimum rank factor analysis

For any given number of factors, Minimum Rank Factor Analysis yields optimal communalities for an observed covariance matrix in the sense that the unexplained common variance with that number of factors is minimized, subject to the constraint that both the diagonal matrix of unique variances and the observed covariance matrix minus that diagonal matrix are positive semidefinite. As a result, it becomes possible to distinguish the explained common variance from the total common variance. The percentage of explained common variance is similar in meaning to the percentage of explained observed variance in Principal Component Analysis, but typically the former is much closer to 100 than the latter. So far, no statistical theory of MRFA has been developed. The present paper is a first start. It yields closed-form expressions for the asymptotic bias of the explained common variance, or, more precisely, of the unexplained common variance, under the assumption of multivariate normality. Also, the asymptotic variance of this bias is derived, and also the asymptotic covariance matrix of the unique variances that define a MRFA solution. The presented asymptotic statistical inference is based on a recently developed perturbation theory of semidefinite programming. A numerical example is also offered to demonstrate the accuracy of the expressions.This work was supported, in part, by grant DMS-0073770 from the National Science Foundation.     

Effects of Performance-Based Pay Systems on Quantity and Quality in Computer Programming

This experiment was conducted to investigate the effects of quality-contingent pay systems on quantity and quality. Three computer science students were paid to create simple computer programs across 25 sessions. A multiple-baseline across subjects design was used to compare the effects of three kinds of pay systems; pay-for-hour, pay-for-quantity, and pay-for-quality systems. The quantity was higher when pay was based on the quantity of the programs produced, and the quality was highest when pay was based on the quality of the programs. The production cost including quality inspection costs was highest when pay was based on the time worked.     

题库智能化组卷的心理计量理论与方法

现代教育成就测验的广泛应用,促使题库技术迅速发展。现代教育测量理论与计算机技术的结合,更使智能化组卷成为可能。本文报告了以项目反应理论为指导,并改进一般线性规划法为分步离差加权模型法,编制程序在高等教育自学考试“逻辑学”题库上,成功实现智能化组卷的研究成果,从而为计算机技术在题库建设中的应用作了新的探讨。     

Answer Sets and Qualitative Optimization

One of the major reasons for the success of answer set programmingin recent years was the shift from a theorem proving to a constraintprogramming view: problems are represented such that stablemodels, respectively answer sets, rather than theorems correspondto solutions. This shift in perspective proved extremely fruitfulin many areas. We believe that going one step further from a"hard" to a "soft" constraint programming paradigm, or, in otherwords, to a paradigm of qualitative optimization, will proveequally fruitful. In this paper we try to support this claimby showing that several generic problems in logic based problemsolving can be understood as qualitative optimization problems,and that these problems have simple and elegant formulationsgiven adequate optimization constructs in the knowledge representationlanguage.     

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.     

Capturing equilibrium models in modal logic

Here-and-there models and equilibrium models were investigated as a semantical framework for answer-set programming by Pearce, Valverde, Cabalar, Lifschitz, Ferraris and others. The semantics of equilibrium logic is given in an indirect way: the notion of an equilibrium model is defined in terms of quantification over here-and-there models. We here give a direct semantics of equilibrium logic, stated for a modal language embedding the language of equilibrium logic.     

Enhancing Digital Fluency through a Training Program for Creative Problem Solving Using Computer Programming

The purpose of this paper is to propose a training program for creative problem solving based on computer programming. The proposed program will encourage students to solve real‐life problems through a creative thinking spiral related to cognitive skills with computer programming. With the goal of enhancing digital fluency through this proposed training program, we investigated its effects. Two sets of experiments were performed in which 119 typical students and 30 younger, gifted students participated. Two synthetic creative problem solving tests, which had a high correlation with logical ability, scientific problem solving ability and divergent thinking ability, were developed to measure creative problem solving ability. We provided the treatment group with a paper‐based booklet with relevant problems developed specifically for that group. ANCOVA statistical procedures were used to analyze the pre‐ and post‐synthetic creative problem solving tests. The findings of our study are as follows: with typical students, the originality of the treatment group outperformed the control group, a result that was compatible with previous research. With gifted students, the fluency of the treatment group outperformed the control group, and overall creative problem solving ability was enhanced. Remarkably, fluency increased significantly, a notable difference from the results of prior studies. In conclusion, we inferred that, given the definition of digital fluency, if creative problem solving ability is enhanced by a training program for creative problem solving based on computer programming, digital fluency will ultimately be improved. In this paper, we discuss the result of fluency enhancement that contradicts prior research. We suggest that this training program could be a new learning environment for the students who have grown up with digital media.