Purdue University
Purdue Links Purdue Home | Purdue Search | Visit Purdue| Giving
Image Spacer
Human Problem Solving: Difficult Optimization Tasks, Workshop



People Involved


Demos and Downloads


Travel and Lodging



Contact Us

Purdue University


Individual Differences in Problem Solving and Intelligence

Author: Nick Burns
Affiliation:University of Adelaide

Studies of human problem solving have traditionally used deterministic tasks that require the execution of a systematic series of steps to reach a rational and optimal solution. Most real-world problems, however, are characterised by uncertainty, the need to consider an enormous number of variables and possible courses of action at each stage in solving the problem, and the need to optimise the solution subject to multiple interacting constraints. There are reliable individual differences in people’s abilities to solve such realistic problems. It also seems likely that people’s ability to solve these difficult problems reflects, or depends on, their intelligence. We report on a study of N = 101 adults who completed a series of visual optimisation problems (Travelling Salesperson, Minimum Spanning Tree, and Generalised Steiner Tree problems), as well as a cognitive optimisation problem (a version of the Secretary problem). We also characterised these individuals along three relevant and important cognitive abilities dimensions, fluid ability, visuo-spatial ability, and cognitive processing speed. Modelling of covariance structures indicated that performance on both types of optimisation problems relies on general intelligence and raises the possibility that they can be used to assess intelligence.

Optimizing and “pessimizing” – human performance with instructional variants of the traveling salesperson problem

Author: Edward P. Chronicle
Affiliation: University of Hawaii at Manoa

The two-dimensional Traveling Salesperson Problem (TSP) requires finding the shortest tour through n locations. Untrained adults are adept at the task, and reliably outperform simple construction algorithms for n ≤ 60. Performance may stem from a specific, inherent ability. Alternatively, it may reflect general spatial intelligence, whether inherent or acquired. If the latter holds, then people should be equally adept at finding longest tours. I report two experiments in which human ability to find shortest and longest tours was examined. In Experiment 1, tour lengths were 6.02% above the minimal for short tours, and 16.23% below the maximal for long tours, with short tour performance significantly superior to long, t(18)=4.30, p<.001. Experiment 2 replicated Experiment 1, and also examined whether humans could perform at the equivalent level to that of construction algorithms when finding longest tours. Full data will be available by the time of the meeting. These results are consistent with the hypothesis of a specific, inherent ability to find short routes, and I will offer some suggestions as to possible origins of this ability.

Human interaction in solving hard practical optimization problems

Author: Richard W. Eglese
Affiliation: Lancaster University, UK

In the field of Operational Research, there are many practical management situations where a mathematical model may be constructed in the form of an optimization model. Many of these models require excessive computing time and resources to produce a guaranteed optimal solution. Heuristic methods are often devised for these hard practical optimization problems to deliver a good, though not necessarily optimal solution, within the computing time available. A key question is whether devising an approach that involves human judgement as part of the solution process is an effective strategy for producing good solutions. This issue is illustrated using a case study concerning the planning of vehicle routes for a winter gritting operation. In this case, a comparison is made of the quality of the solution achieved by allowing human interaction in the solution process compared to a simple heuristic, showing that significant benefits may be obtained from this approach. Further reasons are given and discussed for making use of human interaction in solving hard practical optimization problems and finally some issues for future research in this area are outlined.

Approximating TSP solutions with Graph Pyramids

Authors: Walter G. Kropatsch and Yll Haxhimusa
Affiliation: Vienna University of Technology

The travelling salesperson (TSP) problem consists in finding the shortest tour through n cities. The locations of these cities determine the solution and the difficulty of finding it. There are configurations where a trivial closest neighbor connecting algorithm finds the optimal solution. Pyramid solution strategies convert a TSP problem with a large number of cities into successively smaller problems with similar layout and solution until the number of cities is small enough to seek the optimal solution. Expanding this solution to the lower levels of the pyramid approximates the solution. A dual graph pyramid adapts its structure to the data. A version of Boruvca's minimal spanning tree construction will be applied to the solution of the TSP problem. Inserting further cities along the optimal tour does not change its length. This increases the size of a given TSP problem into a large class where the trivial algorithm finds the original optimal solution. This may be of interest for two reasons: 1) It allows the generation of a large variety of new problems with a known optimal solution. 2) The difficulty of a given TSP problem could be related with the density of cities along the optimal tour.

A generative model of human performance on an optimal stopping problem

Author: Michael D. Lee
Affiliation: University of Adelaide, Australia

We consider human performance on an optimal stopping problem where people are presented with a list numbers independently chosen from a bounded uniform distribution. People are told how many numbers are in the list, and how they were chosen. People are then shown the numbers one at a time, and are instructed to choose the maximum, subject to the constraint that they must choose a number at the time it is presented, and any choice below the maximum is incorrect. We present empirical evidence that suggests people use threshold-based models to make decisions, choosing the first number that exceeds a fixed threshold for that position in the list. We then develop a generative account of this model family, and use Bayesian and Minimum Description Length methods -- including model averaging, model selection and 'entropification' methods -- to learn about the parameters of the generative process, and make inferences about the threshold decision models people use. Finally, we consider a framework for modelling the clear individual differences in the data, and discuss the possibility of modelling group decision-making on a modified version of the optimal stopping task.

Solution performance and heuristics in closed and open versions of 2D Euclidean TSPs

Author: James N. MacGregor
Affiliation: University of Victoria, Canada

We report the results of several previously published experiments and one new experiment comparing optimization performance on closed tours versus open paths. One experiment used instances with 12 nodes having either one or six interior nodes. The results indicated more optimal solutions on closed tours than on open paths, but differences were more pronounced for the one than for the six interior node instances. A second experiment using 15 node instances with 9 interior nodes failed to find a significant difference between closed and open versions, while a third, using 15 node instances with 4 interior nodes, again found closed tour performance to be superior. A fourth experiment, using 20 node problems with 0, 5, 10 and 15 interior points, found results similar to the first experiment, that the superiority of performance on closed versions was greater for fewer interior points. Overall, the results indicate that performance on closed tours degrades with increasing numbers of interior points, while performance on open paths does not. We discuss implications of the results for human heuristics for solving both closed and open versions.

Human solutions to the capacitated vehicle routing problem

Authors: Tom Ormerod & Simon Slavin
Affiliation: Lancaster University, UK

The capacitated vehicle routing problem (CVRP) presents an important example of NP-complete optimization problems, partly because it subsumes travelling sales problems as a special case, but also because of its practical significance to delivery and distribution planning. The CVRPs studied here consist of a set of nodes presented in a 2D Euclidean plane: deliveries must be made to meet different demands from nodes using a finite number of capacity-limited vehicles. We present the results of a series of preliminary studies that examine human-drawn solutions to CVRPs of between 30 and 60 nodes. The studies compare human performance against known optimum solutions, and also examine the effects of visual display of node demand size and training manipulations on improvement to human solutions.

Adaptive pyramid model for the traveling salesman problem

Author: Pizlo, Z., Stefanov, E., Saalweachter, J., Haxhimusa, Y. & Kropatsch, W.G.
Affiliation: Purdue University and Vienna Univ. of Technology

We will present a pyramid model, which provides near-optimal solutions to the Euclidean-TSP in time that is a low-degree polynomial function of the problem size. In this model hierarchical clustering of cities is first performed by using an adaptive method. Specifically, after computing a weighted average I(x,y) of city positions, the algorithm finds the borders between clusters as argmin_x{argmax_y[I(x,y)]} or argmin_y{argmax_x[I(x,y)]}. This process is performed recursively in a coarse-to-fine direction. The solution tour is then produced by a sequence of coarse-to-fine approximations, during which the model has a high-resolution access to the problem representation only within a small area, simulating the non-uniform distribution of visual acuity across the visual field. The tour is produced by simulated movements of the eyes. Computational complexity of the new model is between N and N^2. The model was applied to TSP problems of size 6, 10, 20 and 50 and its performance was fitted to that of five subjects by using one free parameter representing the extent of local search. Computational efficiency of the model was then tested using problems with sizes between 50 and 1000 cities.

Understanding human sequential decision making under uncertainty using ideal observer analysis

Author: Brian J. Stankiewicz
Affiliation: University of Texas, Austin

Most human decisions are made with a certain amount of uncertainty about the true state of the environment and with noisy actions and observations. For example, in medical diagnosis and treatment, a patient will present a collection of symptoms in which the doctor must interpret and generate a hypothesis about the true malady (uncertainty about the true state of the patient). Given these initial observations and the hypotheses that the doctor generated, he/she needs to decide what actions to do. These actions can be gathering more information from the patient (e.g., tests) or prescribing a specific treatment. Furthermore the doctor must weigh the costs and benefits of each of these actions. Once the doctor has decided on the appropriate action the doctor will receive new information that will aid in updating his current belief about the true malady of the patient. The doctor will cycle through this observe, belief update, generate action cycle until the task is completed. We are studying human sequential decision making with uncertainty behavior by studying human performance in problems that are structurally similar to the medical diagnosis problem using a Seek-and-Destroy task and a human navigation when lost task. In both of these studies we compare the human observer to the ideal observer using Partially Observable Markov Decision Process (POMDP). We have worked to isolate the cognitive limitation that are preventing subjects from become optimal decision makers. In summary we have evidence that the cognitive limitation is in the subject's ability to integrate the actions and observations into an accurate belief state about the environment.

Implementing The Tractable-Design Cycle: Definitions and Techniques

Author: Ulrike Stege
Affiliation: University of Victoria, Canada

In her talk, I. van Rooij proposed to utilize a tractable-design cycle in the computational modeling of human optimization behavior. To implement this cycle we need the following two ingredients: (1) a definition of tractability, and (2) techniques for assessing tractability. In this talk I discuss two proposals for defining tractability. The first definition derives from classical complexity theory and defines tractability as polynomial-time computability. On this account NP-hard computations are considered intractable. The second definition derives from parameterized complexity theory and defines tractability as polynomial-time computability for small parameters ranges, called fixed-parameter tractability. On this account NP-hard computation may be tractable for small parameter ranges, even if the input size is large. I will argue that, for our purpose, the second definition improves upon the first. Subsequently, I review a set of rather simple techniques to perform (in)tractability tests and provide examples of how these techniques can be used in the analysis and improvement of existing models of human optimization.

Understanding Human Optimization: The Case for a Tractable-Design Cycle

Author: Iris van Rooij
Affiliation: Eindhoven University of Technology

Optimization models of cognition abound. For example, Eleanor Rosch proposed that humans form object categories so as to maximize within-category similarity and between-category dissimilarity; Paul Thagard proposed that humans make inferences so as to maintain maximally coherent belief networks; Kurt Koffka proposed that humans interpret ambiguous images in the simplest possible way. Formalizations of such optimization models often run into the problem of computational intractability. Intractable optimization models are unsatisfactory, as they seem to exclude any computational understanding of how humans optimize. To deal with this problem, I propose to implement a “tractable-design cycle” (analogous to the well-known “empirical cycle”): Each round we formulate a newly adjusted theory and test it against the tractability criterion. If, at some point, the test comes out positive, we have achieved an understanding of how the behavioral capacity that seemed intractable at first (in light of the old theory) is in fact computationally realizable (in light of the new theory). If, on the other hand, we systematically fail to find a tractable version of the theory, then we have corroborating evidence that the theory is fundamentally flawed. In any event, the tractable-design cycle makes for a better understanding of human optimization abilities and inabilities.

purdue homepage purdue search purdue maps purdue directories Copyright © 2003, Purdue University, all rights reserved. An equal access/equal opportunity university.
Purdue Disclaimer Nondiscrimination Policy