Theoretical comparisons of search strategies in branch-and-bound algorithms

Four known search strategies used in branch-and-bound algorithms-heuristic search, depth-first search, best-bound search, and breadth-first search-are theoretically compared from the viewpoint of the performance of the resulting algorithms. Heuristic search includes the other three as special cases. Since heuristic search is determined by a heuristic functionh, we first investigate how the performance of the resulting algorithms depends onh. In particular, we show that heuristic search is stable in the sense that a slight change inh causes only a slight change in its performance. The best and the worst heurstic functions are clarified, and also discussed is how the heuristic functionh should be modified to obtain a branch-and-bound algorithm with an improved performance. Finally, properties and limitations of depth-first search, best-bound search, and breadth-first search viewed as special cases of heuristic search are considered. In particular, it is shown that the stability observed for heuristic search no longer holds for depth-first search.     

Parallel branch-and-bound search in Parlog

The concurrent logic languages, of which Parlog is one, have been promoted as a new generation of software languages specifically designed for parallel programming. This paper investigates their application to a search problem commonly used as an illustration of artificial intelligence techniques, the 8-puzzle. It notes that programs written in the concurrent logic languages which do not pay attention to the parallelism can fall into two possible traps: either there is little real parallelism in them due to data dependencies, or there is too much parallelism and any practical architecture will be overwhelmed. A solution which controls the parallelism using user-defined priorities is proposed. This solution has the advantage of being architecture-independent.     

Some approaches to improve tree-based nearest neighbour search algorithms

Nearest neighbour search is a widely used technique in pattern recognition. During the last three decades a large number of fast algorithms have been proposed. In this work we are interested in algorithms that can be used with any dissimilarity function provided that it fits the mathematical notion of distance.Some of such algorithms organize, in preprocessing time, the data in a tree structure that is traversed in search time to find the nearest neighbour. The speedup is obtained using some pruning rules that avoid the traversal of some parts of the tree.In this work two new decomposition methods to build the tree and three new pruning rules are explored. The behaviour of our proposal is studied through experiments with synthetic and real data.     

Intelligent scheduling with tabu search: An application to jobs with linear delay penalties and sequence-dependent setup costs and times

In this article we study thetabu search (TS) method in an application for solving an important class of scheduling problems. Tabu search is characterized by integrating artificial intelligence and optimization principles, with particular emphasis on exploiting flexible memory structures, to yield a highly effective solution procedure. We first discuss the problem of minimizing the sum of the setup costs and linear delay penalties when N jobs, arriving at time zero, are to be scheduled for sequential processing on a continuously available machine. A prototype TS method is developed for this problem using the common approach of exchanging the position of two jobs to transform one schedule into another. A more powerful method is then developed that employs insert moves in combination with swap moves to search the solution space. This method and the best parameters found for it during the preliminary experimentation with the prototype procedure are used to obtain solutions to a more complex problem that considers setup times in addition to setup costs. In this case, our procedure succeeded in finding optimal solutions to all problems for which these solutions are known and a better solution to a larger problem for which optimizing procedures exceeded a specified time limit (branch and bound) or reached a memory overflow (branch and bound/dynamic programming) before normal termination. These experiments confirm not only the effectiveness but also the robustness of the TS method, in terms of the solution quality obtained with a common set of parameter choices for two related but different problems.     

A heuristic and a branch-and-bound algorithm for the Assembly Line Worker Assignment and Balancing Problem

In traditional assembly lines, it is reasonable to assume that task execution times are the same for each worker. However, in Sheltered Work Centres for Disabled this assumption is not valid: some workers may execute some tasks considerably slower or even be incapable of executing them. Worker heterogeneity leads to a problem called the Assembly Line Worker Assignment and Balancing Problem (ALWABP). For a fixed number of workers the problem is to maximize the production rate of an assembly line by assigning workers to stations and tasks to workers, while satisfying precedence constraints between the tasks.This paper introduces new heuristic and exact methods to solve this problem. We present a new MIP model, propose a novel heuristic algorithm based on beam search, as well as a task-oriented branch-and-bound procedure which uses new reduction rules and lower bounds for solving the problem. Extensive computational tests on a large set of instances show that these methods are effective and improve over existing ones.     

Approximate branch-and-bound global optimization using B-spline hypervolumes

This paper presents a B-spline-based branch-and-bound algorithm for unconstrained global optimization. The key components of the branch-and-bound, a well-known algorithm paradigm for global optimization, are a subdivision scheme and a bound calculation scheme. For these schemes, we first introduce a B-spline hypervolume to approximate an objective function defined in a design space, where the approximation is based on Latin-hypercube sampling points. We then describe a proposed algorithm for finding global solutions approximately within a prescribed tolerance. The algorithm includes two procedures that are performed iteratively until all stopping conditions are satisfied. One involves subdivision into mutually disjoint subspaces and computation of their bound information, both of which are accomplished by using B-spline hypervolumes. The other updates a search tree that represents a hierarchical structure of subdivided subspaces during the solution process. Finally, we examine the computational performance of the proposed algorithm on various test problems that cover most of the difficulties encountered in global optimization. The results show that the proposed algorithm is complete without using heuristics and has good potential for application in large-scale NP-hard optimization.     

Partial match queries in relaxed multidimensional search trees

Partial match queries arise frequently in the context of large databases, where each record contains a distinct multidimensional key, that is, the key of each record is aK-tuple of values. The components of a key are called thecoordinates orattributes of the key. In a partial match query we specify the value ofs attributes, 0<s<K, and leave the remainingK —s attributes unspecified. The goal is to retrieve all the records in the database that match the specified attributes. In this paper we present several results about the average performance and variance of partial matches in relaxedK-dimensional trees (search trees and digital tries). These data structures are variants of the well knownK d-trees andK d-tries. In relaxed trees the sequence of attributes used to guide a query is explicitly stored at the nodes of the tree and randomly generated and, in general, will be different for different search paths. In the standard variants, the sequence of attributes that guides a query examines the attributes in a cyclic fashion, fixed and identical for all search paths. We show that the probabilistic analysis of the relaxed multidimensional trees is very similar to that of standardK d-trees andK d-tries, and also to the analysis of quadtrees. In fact, besides the average cost and variance of partial match in relaxedK d-trees andK d-tries, we also obtain the variance of partial matches in two-dimensional quadtrees. We also compute the average cost of partial matches in other relaxed multidimensional digital tries, namely, relaxedK d-Patricia and relaxedK d-digital search trees. This research was supported by Acciones Integradas Hispano-Austríacas HU1997-0016 (Austrian-Spanish Scientific Exchange Program). The first author was also supported by ESPRIT LTR 20244 (ALCOM IT), CICYT TIC97-1475-CE, DGES PB95-0787 (KOALA), and CIRIT 1997SGR-00366 (SGR). The second author was also supported by the Austrian Research Society (FWF) under Project P12599-MAT. Online publication October 13, 2000.     

Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.     

An elitist self-adaptive step-size search for structural design optimization

This paper presents a method for optimal sizing of truss structures based on a refined self-adaptive step-size search (SASS) algorithm. An elitist self-adaptive step-size search (ESASS) algorithm is proposed wherein two approaches are considered for improving (i) convergence accuracy, and (ii) computational efficiency. In the first approach an additional randomness is incorporated into the sampling step of the technique to preserve exploration capability of the algorithm during the optimization. Furthermore, an adaptive sampling scheme is introduced to enhance quality of the final solutions. In the second approach computational efficiency of the technique is accelerated through avoiding unnecessary analyses throughout the optimization process using the so-called upper bound strategy (UBS). The numerical results indicate the efficiency of the proposed ESASS algorithm.     

Heuristic evaluation functions in artificial intelligence search algorithms

We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, involve an adversarial relationship between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired.     

A comparative analysis of genetic algorithms and directed grid search for parametric optimization

In this paper, a comparative analysis of the performance of the Genetic Algorithm (GA) and Directed Grid Search (DGS) methods for optimal parametric design is presented. A genetic algorithm is a guided random search mechanism based on the principle of natural selection and population genetics. The Directed Grid Search method uses a selective directed search of grid points in the direction of descent to find the minimum of a real function, when the initial estimate of the location of the minimum and the bounds of the design variables are specified. An experimental comparison and a discussion on the performance of these two methods in solving a set of eight test functions is presented.     

Visual and memory search in complex environments: determinants of eye movements and search performance

Previous research on visual and memory search revealed various top down and bottom up factors influencing performance. However, utilising abstract stimuli (e.g. geometrical shapes or letters) and focussing on individual factors has often limited the applicability of research findings. Two experiments were designed to analyse which attributes of a product facilitate search in an applied environment. Participants scanned displays containing juice packages while their eye movements were recorded. The familiarity, saliency, and position of search targets were systematically varied. Experiment 1 involved a visual search task, whereas Experiment 2 focussed on memory search. The results showed that bottom up (target saliency) and top down (target familiarity) factors strongly interacted. Overt visual attention was influenced by cultural habits, purposes, and current task demands. The results provide a solid database for assessing the impact and interplay of fundamental top down and bottom up determinants of search processes in applied fields of psychology. Practitioner Summary: Our study demonstrates how a product (or a visual item in general) needs to be designed and placed to ensure that it can be found effectively and efficiently within complex environments. Corresponding product design should result in faster and more accurate visual and memory based search processes.     

Large neighbourhood search algorithms for the founder sequence reconstruction problem

The reconstruction of founder genetic sequences of a population is a relevant issue in evolutionary biology research. The problem consists in finding a biologically plausible set of genetic sequences (founders), which can be recombined to obtain the genetic sequences of the individuals of a given population. The reconstruction of these sequences can be modelled as a combinatorial optimisation problem in which one has to find a set of genetic sequences such that the individuals of the population under study can be obtained by recombining founder sequences minimising the number of recombinations. This problem is called the founder sequence reconstruction problem. Solving this problem can contribute to research in understanding the origins of specific genotypic traits. In this paper, we present large neighbourhood search algorithms to tackle this problem. The proposed algorithms combine a stochastic local search with a branch-and-bound algorithm devoted to neighbourhood exploration. The developed algorithms are thoroughly evaluated on three different benchmark sets and they establish the new state of the art for realistic problem instances.     

A space search optimization algorithm with accelerated convergence strategies

Evolutionary algorithms (EAs), which have been widely used to solve various scientific and engineering optimization problems, are essentially stochastic search algorithms operating in the overall solution space. However, such random search mechanism may lead to some disadvantages such as a long computing time and premature convergence. In this study, we propose a space search optimization algorithm (SSOA) with accelerated convergence strategies to alleviate the drawbacks of the purely random search mechanism. The overall framework of the SSOA involves three main search mechanisms: local space search, global space search, and opposition-based search. The local space search that aims to form new solutions approaching the local optimum is realized based on the concept of augmented simplex method, which exhibits significant search abilities realized in some local space. The global space search is completed by Cauchy searching, where the approach itself is based on the Cauchy mutation. This operation can help the method avoid of being trapped in local optima and in this way alleviate premature convergence. An opposition-based search is exploited to accelerate the convergence of space search. This operator can effectively reduce a substantial computational overhead encountered in evolutionary algorithms (EAs). With the use of them SSOA realizes an effective search process. To evaluate the performance of the method, the proposed SSOA is contrasted with a method of differential evolution (DE), which is a well-known space concept-based evolutionary algorithm. When tested against benchmark functions, the SSOA exhibits a competitive performance vis-a-vis performance of some other competitive schemes of differential evolution in terms of accuracy and speed of convergence, especially in case of high-dimensional continuous optimization problems.     

A hybrid scatter search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem (PTSP) is an important theoretical and practical topic in the study of stochastic network problems. It provides researchers with a modeling framework for exploring the stochastic effects in routing problems. This paper focuses on developing the hybrid scatter search (HSS) by incorporating the nearest neighbor rule (NNR), threshold accepting (TA) and edge recombination (ER) crossover into a scatter search conceptual framework to solve the PTSP. A set of numerical experiments were conducted to test the validity of the HSS based on the test problems from Tang and Miller-Hooks’ study. The numerical results showed that the HSS can effectively solve the PTSP in most of the tested cases in terms of objective function value. Moreover, the results also indicated that incorporating threshold accepting into the scatter search framework can further increase the computation efficiency while maintaining solution quality. These findings show the potential of the proposed HSS in solving the large-scale PTSP.     

Solution counting algorithms for constraint-centered search heuristics

Constraints have played a central role in cp because they capture key substructures of a problem and efficiently exploit them to boost inference. This paper intends to do the same thing for search, proposing constraint-centered heuristics which guide the exploration of the search space toward areas that are likely to contain a high number of solutions. We first propose new search heuristics based on solution counting information at the level of individual constraints. We then describe efficient algorithms to evaluate the number of solutions of two important families of constraints: occurrence counting constraints, such as alldifferent, and sequencing constraints, such as regular. In both cases we take advantage of existing filtering algorithms to speed up the evaluation. Experimental results on benchmark problems show the effectiveness of our approach. An earlier version of this paper appeared as [24].     

Multiple- and single-objective approaches to laminate optimization with genetic algorithms

In this paper an application of a genetic algorithm to a material- and sizing-optimization problem of a plate is described. This approach has obvious advantages: it does not require any derivative information and it does not impose any restriction, in terms of convexity, on the solution space. The plate optimization problem is firstly formulated as a constrained mixed-integer programming problem with a single objective function. An alternative multiobjective formulation of the problem in which some constraints are included as additional objectives is also presented. Some numerical results are included that show the appropriateness of the algorithm and of the mathematical model for the solution of this optimization problem, as well as the superiority of the multiobjective approach.