Human performance on visually presented Traveling Salesman problems

Little research has been carried out on human performance in optimization problems, such as the Traveling Salesman problem (TSP). Studies by Polivanova (1974, Voprosy Psikhologii, 4, 41–51) and by MacGregor and Ormerod (1996, Perception & Psychophysics, 58, 527–539) suggest that: (1) the complexity of solutions to visually presented TSPs depends on the number of points on the convex hull; and (2) the perception of optimal structure is an innate tendency of the visual system, not subject to individual differences. Results are reported from two experiments. In the first, measures of the total length and completion speed of pathways, and a measure of path uncertainty were compared with optimal solutions produced by an elastic net algorithm and by several heuristic methods. Performance was also compared under instructions to draw the shortest or the most attractive pathway. In the second, various measures of performance were compared with scores on Raven's advanced progressive matrices (APM). The number of points on the convex hull did not determine the relative optimality of solutions, although both this factor and the total number of points influenced solution speed and path uncertainty. Subjects' solutions showed appreciable individual differences, which had a strong correlation with APM scores. The relation between perceptual organization and the process of solving visually presented TSPs is briefly discussed, as is the potential of optimization for providing a conceptual framework for the study of intelligence. Received: 28 December 1998 / Accepted: 20 January 2000     

A note on the estimation of the Pareto efficient set for multiobjective matrix permutation problems

There are a number of important problems in quantitative psychology that require the identification of a permutation of the n rows and columns of an n × n proximity matrix. These problems encompass applications such as unidimensional scaling, paired‐comparison ranking, and anti‐Robinson forms. The importance of simultaneously incorporating multiple objective criteria in matrix permutation applications is well recognized in the literature; however, to date, there has been a reliance on weighted‐sum approaches that transform the multiobjective problem into a single‐objective optimization problem. Although exact solutions to these single‐objective problems produce supported Pareto efficient solutions to the multiobjective problem, many interesting unsupported Pareto efficient solutions may be missed. We illustrate the limitation of the weighted‐sum approach with an example from the psychological literature and devise an effective heuristic algorithm for estimating both the supported and unsupported solutions of the Pareto efficient set.     

Detecting local convexity on the pareto surface

Recent regain in interest in multi‐criteria optimization approaches to provide a designer with multiple solutions to select from and support decisions has led to various methodologies to generate such solutions and possibly approximate the Pareto set. This paper introduces the notions of H‐ and w‐convexities, and develops a simple method to identify local convexity of Pareto hyper‐surfaces since their shape can dictate the choice of the method to use to obtain Pareto solutions and possibly to build an approximation of that set. The method is based on comparing the results from the weighting method to those of the Tchebycheff method at any point on the Pareto hyper‐surface. If, under some conditions, the points obtained from the two methods are identical or not, a local convexity or its lack can be assumed at that location and in its immediate neighbourhood. A numerical example is included. Copyright © 2002 John Wiley & Sons, Ltd.     

Order-Constrained Solutions in <Emphasis Type="Italic">K</Emphasis>-Means Clustering: Even Better Than Being Globally Optimal

This paper proposes an order-constrained K-means cluster analysis strategy, and implements that strategy through an auxiliary quadratic assignment optimization heuristic that identifies an initial object order. A subsequent dynamic programming recursion is applied to optimally subdivide the object set subject to the order constraint. We show that although the usual K-means sum-of-squared-error criterion is not guaranteed to be minimal, a true underlying cluster structure may be more accurately recovered. Also, substantive interpretability seems generally improved when constrained solutions are considered. We illustrate the procedure with several data sets from the literature.     

Uniform Test Assembly

In educational practice, a test assembly problem is formulated as a system of inequalities induced by test specifications. Each solution to the system is a test, represented by a 0–1 vector, where each element corresponds to an item included (1) or not included (0) into the test. Therefore, the size of a 0–1 vector equals the number of items n in a given item pool. All solutions form a feasible set—a subset of 2 ⁿ vertices of the unit cube in an n-dimensional vector space. Test assembly is uniform if each test from the feasible set has an equal probability of being assembled. This paper demonstrates several important applications of uniform test assembly for educational practice. Based on Slepian’s inequality, a binary program was analytically studied as a candidate for uniform test assembly. The results of this study establish a connection between combinatorial optimization and probability inequalities. They identify combinatorial properties of the feasible set that control the uniformity of the binary programming test assembly. Computer experiments illustrating the concepts of this paper are presented.     

Comparing graphic and symbolic classification in interactive multiobjective optimization

In interactive multiobjective optimization systems, the classification of objective functions is a convenient way to direct the solution process in order to search for new, more satisfactory, solutions in the set of Pareto optimal solutions. Classification means that the decision maker assigns the objective functions into classes depending on what kind of changes in their values (in relation to the current values) are desirable. Here we study the role of user interfaces in implementing classification in multiobjective optimization software and how classification should be realized. In this way, we want to pay attention to the usability of multiobjective optimization software. Typically, this topic has not been of interest in the multiobjective optimization literature. However, usability aspect is important because in interactive classification‐based multiobjective optimization methods, the classification is the core of the solution process. We can say that the more convenient the classification is, the more efficient the system or the method is and the better it supports the work of the decision maker. We report experiments with two classification options, graphic and symbolic ones, which are used in connection with an interactive multiobjective optimization system WWW‐NIMBUS. The ideas and conclusions given are applicable for other interactive classification‐based method, as well. Copyright © 2005 John Wiley & Sons, Ltd.     

The Entangling of Problems,Solutions and Markets: On Building a Market for Privacy

An increasing number of public problems have been subject to market-based interventions as solutions. However, the relationship between problems and solutions in market-based interventions is complex. On occasions solutions are reformulated as understanding of the nature of the problem are advanced. Alternatively, problems are reconfigured to fit a standard solution. Or solutions are said to generate numerous new problems. The complex entangling of problems, solutions and markets can be explored by focusing on the field of online privacy. The complexities of this field can be analysed through three science and technology studies (STS) treatments of problems and solutions. First, issue-problematisation can be used to understand the ways in which a problem is assembled and comes to form the focus for discussion as an issue. Second, a paradigm-exemplar approach can assess the extent to which a particular coupling of problem and solution becomes an exemplar for others to draw on. Third, ontological constitution provides a focal point for analysing the ways in which the very nature of entities involved in problems, solutions and markets can be considered. There is analytic utility in each of these approaches in engaging with online privacy regulation and the emerging role of start-ups in introducing new privacy products to an emerging market place. However, these STS approaches leave us with questions regarding the relationship between market solutions and publics, the co-ordination of entities in market solutions and the normative questions that arise from entangling markets, problems and solutions.     

Tests of statistical hypotheses in the case of unequal or disproportionate numbers of observations in the subclasses

General solutions of the analysis of variance in the case of unequal numbers of observations in the subclasses are presented. If we havek criteria for the classification, there will bek! solutions in making a complete analysis and 2^k–1 answers, bearing different meanings, for the sum of squares between subclasses of each criterion. The sum of squares for the interaction of any order, however, will be identical in different solutions of same problem.     

Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization

This paper presents a multiple-objective metaheuristic procedure—Pareto simulated annealing. The goal of the procedure is to find in a relatively short time a good approximation of the set of efficient solutions of a multiple-objective combinatorial optimization problem. The procedure uses a sample, of so-called generating solutions. Each solution explores its neighbourhood in a way similar to that of classical simulated annealing. Weights of the objectives, used for their local aggregation, are tuned in each iteration in order to assure a tendency for approaching the efficient solutions set while maintaining a uniform distribution of the generating solutions over this set. A computational experiment shows that the method is a better tool for approximating the efficient set than some previous proposals. © 1998 John Wiley & Sons, Ltd.     

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.     

Optimization and improvement

Agents face serious obstacles to making optimal decisions. For instance, their cognitive limits stand in the way. John Pollock’s book, Thinking about Acting, suggests many ways of revising decision principles to accommodate human limits and to direct limited, artificial agents. The book’s main proposal is to replace optimization, or expected-utility maximization, with locally global planning. This essay describes optimization and locally global planning, and then argues that optimization among salient options has the virtues of locally global planning without certain drawbacks. Although it does not endorse locally global planning, it recommends that decision theory incorporate some of the book’s ideas about settling for improvements when optimization among all options is unrealistic.     

Moving arms: the effects of sensorimotor information on the problem-solving process

Embodied cognition postulates a bi-directional link between the human body and its cognitive functions. Whether this holds for higher cognitive functions such as problem solving is unknown. We predicted that arm movement manipulations performed by the participants could affect the problem-solving solutions. We tested this prediction in quantitative reasoning tasks that allowed two solutions to each problem (addition or subtraction). In two studies with healthy adults (N?=?53 and N?=?50), we found an effect of problem-congruent movements on problem solutions. Consistent with embodied cognition, sensorimotor information gained via right or left arm movements affects the solution in different types of problem-solving tasks.     

Automated Simultaneous Assembly for Multistage Testing

This article offers some solutions used in the assembly of the computerized Uniform Certified Public Accountancy (CPA) licensing examination as practical alternatives for operational programs producing large numbers of forms. The Uniform CPA examination was offered as an adaptive multistage test (MST) beginning in April of 2004. Examples of automated assembly using mixed integer programming (MIP) solutions in Optimization Programming Language software (OPL Studio 3.6.1©, ILOG Inc., Gentilly, France) illustrate MST design features and implementation strategies that can be generalized to other testing programs. This article affords a compromise between the best possible combination of test content and sustainability and security over time by linear programming techniques that make use of mixed integer optimization algorithms. Relative optimization functions are formulated to ensure a variety of constraints are always met for "testlets" of differing difficulties to form panels for the MST design. Technical information is discussed to assist other practitioners and researchers with test assembly optimization problems. Some practical consequences from the selection of statistical targets on testlet exposure are illustrated. These results are described with respect to the fundamental principles of automated test assembly and continuous administration based on MST when testlet or item exposure and inventory rotation are critical concerns.     

Dynamic decision making: a comparison of approaches

This paper is concerned with a specific type of problem, namely dynamic decisions, for which most techniques fail to provide adequate solutions. Here, we present two of the most promising optimization techniques, partially observable Markov decision processes (POMDP) and dynamic decision networks (DDN), while arguing which is the most suitable for this problem domain. Copyright © 2000 John Wiley & Sons, Ltd.     

Linear relations amongk sets of variables

A family of solutions for linear relations amongk sets of variables is proposed. It is shown how these solutions apply fork=2, and how they can be generalized from there tok3.The family of solutions depends on three independent choices: (i) to what extent a solution may be influenced by differences in variances of components within each set; (ii) to what extent the sets may be differentially weighted with respect to their contribution to the solution—including orthogonality constraints; (iii) whether or not individual sets of variables may be replaced by an orthogonal and unit normalized basis.Solutions are compared with respect to their optimality properties. For each solution the appropriate stationary equations are given. For one example it is shown how the determinantal equation of the stationary equations can be interpreted.     

An improved stochastic EM algorithm for large-scale full-information item factor analysis

In this paper, we explore the use of the stochastic EM algorithm (Celeux & Diebolt (1985) Computational Statistics Quarterly, 2, 73) for large-scale full-information item factor analysis. Innovations have been made on its implementation, including an adaptive-rejection-based Gibbs sampler for the stochastic E step, a proximal gradient descent algorithm for the optimization in the M step, and diagnostic procedures for determining the burn-in size and the stopping of the algorithm. These developments are based on the theoretical results of Nielsen (2000, Bernoulli, 6, 457), as well as advanced sampling and optimization techniques. The proposed algorithm is computationally efficient and virtually tuning-free, making it scalable to large-scale data with many latent traits (e.g. more than five latent traits) and easy to use for practitioners. Standard errors of parameter estimation are also obtained based on the missing-information identity (Louis, 1982, Journal of the Royal Statistical Society, Series B, 44, 226). The performance of the algorithm is evaluated through simulation studies and an application to the analysis of the IPIP-NEO personality inventory. Extensions of the proposed algorithm to other latent variable models are discussed.     

The effect of additional variables on factor indeterminacy in models with a single common factor

Determinate solutions for the indeterminate common factor ofp variables satisfying the single common factor model are not unique. Therefore an infinite sequence of additional variables that conform jointly with the originalp variables to the original single common factor model does not determine a unique solution for the indeterminate factor of thep variables (although the solution is unique for the factor of the infinite sequence). Other infinite sequences may be found to determine different solutions for the factor of the originalp variables. The paper discusses a number of theorems about the effects of additional variables on factor indeterminacy in a model with a single common factor and draws conclusions from them for factor theory in general.     

How experimental algorithmics can benefit from Mayo’s extensions to Neyman–Pearson theory of testing

Although theoretical results for several algorithms in many application domains were presented during the last decades, not all algorithms can be analyzed fully theoretically. Experimentation is necessary. The analysis of algorithms should follow the same principles and standards of other empirical sciences. This article focuses on stochastic search algorithms, such as evolutionary algorithms or particle swarm optimization. Stochastic search algorithms tackle hard real-world optimization problems, e.g., problems from chemical engineering, airfoil optimization, or bio-informatics, where classical methods from mathematical optimization fail. Nowadays statistical tools that are able to cope with problems like small sample sizes, non-normal distributions, noisy results, etc. are developed for the analysis of algorithms. Although there are adequate tools to discuss the statistical significance of experimental data, statistical significance is not scientifically meaningful per se. It is necessary to bridge the gap between the statistical significance of an experimental result and its scientific meaning. We will propose some ideas on how to accomplish this task based on Mayo’s learning model (NPT*).     

Mapclus: A mathematical programming approach to fitting the adclus model

We present a new algorithm, MAPCLUS (MAthematicalProgrammingCLUStering), for fitting the Shepard-Arabie ADCLUS (forADditiveCLUStering) model. MAPCLUS utilizes an alternating least squares method combined with a mathematical programming optimization procedure based on a penalty function approach, to impose discrete (0,1) constraints on parameters defining cluster membership. This procedure is supplemented by several other numerical techniques (notably a heuristically based combinatorial optimization procedure) to provide an efficient general-purpose computer implemented algorithm for obtaining ADCLUS representations. MAPCLUS is illustrated with an application to one of the examples given by Shepard and Arabie using the older ADCLUS procedure. The MAPCLUS solution uses half as many clusters to achieve nearly the same level of goodness-of-fit. Finally, we consider an extension of the present approach to fitting a three-way generalization of the ADCLUS model, called INDCLUS (INdividualDifferencesCLUStering).We are indebted to Scott A. Boorman, W. K. Estes, J. A. Hartigan, Lawrence J. Hubert, Carol L. Krumhansl, Joseph B. Kruskal, Sandra Pruzansky, Roger N. Shepard, Edward J. Shoben, Sigfrid D. Soli, and Amos Tversky for helpful discussions of this work, as well as the anonymous referees for their suggestions and corrections on an earlier version of this paper. We are also grateful to Pamela Baker and Dan C. Knutson for technical assistance. The research reported here was supported in part by LEAA Grant 78-NI-AX-0142 and NSF Grants SOC76-24512 and SOC76-24394.     

A Framework for Riddles about Truth that do not involve Self-Reference

In this paper, we present a framework in which we analyze three riddles about truth that are all (originally) due to Smullyan. We start with the riddle of the yes-no brothers and then the somewhat more complicated riddle of the da-ja brothers is studied. Finally, we study the Hardest Logic Puzzle Ever (HLPE). We present the respective riddles as sets of sentences of quotational languages, which are interpreted by sentence-structures. Using a revision-process the consistency of these sets is established. In our formal framework we observe some interesting dissimilarities between HLPE’s available solutions that were hidden due to their previous formulation in natural language. Finally, we discuss more recent solutions to HLPE which, by means of self-referential questions, reduce the number of questions that have to be asked in order to solve HLPE. Although the essence of the paper is to introduce a framework that allows us to formalize riddles about truth that do not involve self-reference, we will also shed some formal light on the self-referential solutions to HLPE.