SSPMO: A Scatter Tabu Search Procedure for Non-Linear Multiobjective Optimization

We describe the development and testing of a metaheuristic procedure, based on the scatter-search methodology, for the problem of approximating the efficient frontier of nonlinear multiobjective optimization problems with continuous variables. Recent applications of scatter search have shown its merit as a global optimization technique for single-objective problems. However, the application of scatter search to multiobjective optimization problems has not been fully explored in the literature. We test the proposed procedure on a suite of problems that have been used extensively in multiobjective optimization. Additional tests are performed on instances that are an extension of those consid…

Erratum to: Scatter Search – Methodology and Implementations in C

Heuristic solutions to the problem of routing school buses with multiple objectives

In this paper we address the problem of routing school buses in a rural area. We approach this problem with a node routing model with multiple objectives that arise from conflicting viewpoints. From the point of view of cost, it is desirable to minimise the number of buses used to transport students from their homes to school and back. From the point of view of service, it is desirable to minimise the time that a given student spends en route. The current literature deals primarily with single-objective problems and the models with multiple objectives typically employ a weighted function to combine the objectives into a single one. We develop a solution procedure that considers each objecti…

Minimizing weighted tardiness of jobs with stochastic interruptions in parallel machines

Abstract In this paper, we address the problem of minimizing expected total weighted tardiness of jobs that have stochastic interruptions and that are processed on a set of parallel machines. Our research generalizes the problem of scheduling parallel machines to minimize total weighted tardiness. The proposed solution method is based on the scatter search methodology and implements an innovative structured combination procedure. Extensive computational testing with more than 400 problem instances shows the merit of the proposed solution method.

Use of Memory in Scatter Search

Heuristics and meta-heuristics for 2-layer straight line crossing minimization

AbstractThis paper presents extensive computational experiments to compare 12 heuristics and 2 meta-heuristics for the problem of minimizing straight-line crossings in a 2-layer graph. These experiments show that the performance of the heuristics (largely based on simple ordering rules) drastically deteriorates as the graphs become sparser. A tabu search metaheuristic yields the best results for relatively dense graphs, with a GRASP implementation as close second. Furthermore, the GRASP approach outperforms all other approaches when tackling low-density graphs.

Principles of scatter search

Scatter search is an evolutionary method that has been successfully applied to hard optimization problems. The fundamental concepts and principles of the method were first proposed in the 1970s, based on formulations dating back to the 1960s for combining decision rules and problem constraints. In contrast to other evolutionary methods like genetic algorithms, scatter search is founded on the premise that systematic designs and methods for creating new solutions afford significant benefits beyond those derived from recourse to randomization. It uses strategies for search diversification and intensification that have proved effective in a variety of optimization problems. This paper provides…

Scatter Search and Path Relinking: Foundations and Advanced Designs

Scatter Search and its generalized form Path Relinking, are evolutionary methods that have been successfully applied to hard optimization problems. Unlike genetic algorithms, they operate on a small set of solutions and employ diversification strategies of the form proposed in Tabu Search, which give precedence to strategic learning based on adaptive memory, with limited recourse to randomization. The fundamental concepts and principles were first proposed in the 1970s as an extension of formulations, dating back to the 1960s, for combining decision rules and problem constraints. (The constraint combination approaches, known as surrogate constraint methods, now independently provide an impo…

Context-Independent Scatter and Tabu Search for Permutation Problems

In this paper, we develop a general-purpose heuristic for permutations problems. The procedure is based on the scatter-search and tabu-search methodologies and treats the objective-function evaluation as a black box, making the search algorithm context-independent. Therefore, our main contribution consists of the development and testing of a procedure that uses no knowledge from the problem context to search for the optimal solution. We perform computational experiments with four well-known permutation problems to study the efficiency and effectiveness of the proposed method. These experiments include a comparison with two commercially available software packages that are also based on met…

Commercial Scatter Search Implementation

In this chapter we discuss the development of commercial optimization software based on the scatter search methodology.

A genetic algorithm for the minimum generating set problem

Graphical abstractDisplay Omitted HighlightsWe propose a novel formulation for the MGS problem based on multiple knapsack.The so-conceived MGS problem is solved by a novel GA.The GA embeds an intelligent construction method and specialized crossover operators.We perform a thorough comparison with regards to state-of-the-art algorithms.The proposal proves to be very competitive, specially for large and hard instances. Given a set of positive integers S, the minimum generating set problem consists in finding a set of positive integers T with a minimum cardinality such that every element of S can be expressed as the sum of a subset of elements in T. It constitutes a natural problem in combinat…

The OptQuest Callable Library

In this chapter we discuss the development and application of a library of functions that is the optimization engine for the OptQuest system. OptQuest is commercial software designed for optimizing complex systems, such as those formulated as simulation models. OptQuest has been integrated with several simulation packages with the goal of adding optimization capabilities. The optimization technology within OptQuest is based on the metaheuristic framework known as scatter search. In addition to describing the functionality of the OptQuest Callable Library (OCL) with an illustrative example, we apply it to a set of unconstrained nonlinear optimization problems.

Black-Box Solvers

Linear programming is perhaps the best-known tool for optimization. Linear programming is a general-purpose framework that allows a real system to be abstracted as a model with a linear objective function subject to a set of linear constraints.

Scatter Search Applications

This section provides a collection of “vignettes” that briefly summarize applications of scatter search (SS) and path relinking (PR) in a variety of settings.

Black box scatter search for general classes of binary optimization problems

The purpose of this paper is to apply the scatter search methodology to general classes of binary problems. We focus on optimization problems for which the solutions are represented as binary vectors and that may or may not include constraints. Binary problems arise in a variety of settings, including engineering design and statistical mechanics (e.g., the spin glass problem). A distinction is made between two sets of general constraint types that are handled directly by the solver and other constraints that are addressed via penalty functions. In both cases, however, the heuristic treats the objective function evaluation as a black box. We perform computational experiments with four well-k…

Models and solution methods for the uncapacitatedr-allocationp-hub equitable center problem

Hub networks are commonly used in telecommunications and logistics to connect origins to destinations in situations where a direct connection between each origin–destination (o-d) pair is impractical or too costly. Hubs serve as switching points to consolidate and route traffic in order to realize economies of scale. The main decisions associated with hub-network problems include (1) determining the number of hubs (p), (2) selecting the p-nodes in the network that will serve as hubs, (3) allocating non-hub nodes (terminals) to up to r-hubs, and (4) routing the pairwise o-d traffic. Typically, hub location problems include all four decisions while hub allocation problems assume that the valu…

Hybridizing the cross-entropy method: An application to the max-cut problem

Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.

Scatter search for the profile minimization problem

We study the problem of minimizing the profile of a graph and develop a solution method by following the tenets of scatter search. Our procedure exploits the network structure of the problem and includes strategies that produce a computationally efficient and agile search. Among several mechanisms, our search includes path relinking as the basis for combining solutions to generate new ones. The profile minimization problem PMP is NP-Hard and has relevant applications in numerical analysis techniques that rely on manipulating large sparse matrices. The problem was proposed in the early 1970s but the state-of-the-art does not include a method that could be considered powerful by today's compu…

Scatter Search and Path Relinking: Advances and Applications

Scatter search (SS) is a population-based method that has recently been shown to yield promising outcomes for solving combinatorial and nonlinear optimization problems. Based on formulations originally proposed in the 1960s for combining decision rules and problem constraints, SS uses strategies for combining solution vectors that have proved effective in a variety of problem settings. Path relinking (PR) has been suggested as an approach to integrate intensification and diversification strategies in a search scheme. The approach may be viewed as an extreme (highly focused) instance of a strategy that seeks to incorporate attributes of high quality solutions, by creating inducements to favo…

Scatter tabu search for multiobjective clustering problems

We propose a hybrid heuristic procedure based on scatter search and tabu search for the problem of clustering objects to optimize multiple criteria. Our goal is to search for good approximations of the efficient frontier for this class of problems and provide a means for improving decision making in multiple application areas. Our procedure can be viewed as an extension of SSPMO (a scatter search application to nonlinear multiobjective optimization) to which we add new elements and strategies specially suited for combinatorial optimization problems. Clustering problems have been the subject of numerous studies; however, most of the work has focused on single-objective problems. Clustering u…

Adaptive memory programming for constrained global optimization

The problem of finding a global optimum of a constrained multimodal function has been the subject of intensive study in recent years. Several effective global optimization algorithms for constrained problems have been developed; among them, the multi-start procedures discussed in Ugray et al. [1] are the most effective. We present some new multi-start methods based on the framework of adaptive memory programming (AMP), which involve memory structures that are superimposed on a local optimizer. Computational comparisons involving widely used gradient-based local solvers, such as Conopt and OQNLP, are performed on a testbed of 41 problems that have been used to calibrate the performance of su…

Tabu search with strategic oscillation for the maximally diverse grouping problem

We propose new heuristic procedures for the maximally diverse grouping problem (MDGP). This NP-hard problem consists of forming maximally diverse groups—of equal or different size—from a given set of elements. The most general formulation, which we address, allows for the size of each group to fall within specified limits. The MDGP has applications in academics, such as creating diverse teams of students, or in training settings where it may be desired to create groups that are as diverse as possible. Search mechanisms, based on the tabu search methodology, are developed for the MDGP, including a strategic oscillation that enables search paths to cross a feasibility boundary. We evaluate co…

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in bot…

Introduction to Spreadsheet Modeling and Metaheuristics

Models, as a simplified representation of reality, are used daily in an attempt to control or understand some aspects of a real system. Simplification of reality is the accepted view of the modeling process, which assumes that reality represents the absolute truth. Without getting too deep into a philosophical discourse, it is worth mentioning the notion of model-dependent realism, a phrase coined by physicists Stephen Hawkings and Leonard Molinow in their book The Grand Design. Model-dependent realism “is based on the idea that our brains interpret the input from our sensory organs by making a model of the world to aid in the decision-making process.” This implies that more than one model …

Metaheuristic procedures for the lexicographic bottleneck assembly line balancing problem

The goal of this work is to develop an improved procedure for the solution of the lexicographic bottleneck variant of the assembly line balancing problem (LB-ALBP). The objective of the LB-ALBP is to minimize the workload of the most heavily loaded workstation, followed by the workload of the second most heavily loaded workstation and so on. This problem-recently introduced to the literature (Pastor, 2011)-has practical relevance to manufacturing facilities. We design, implement and fine-tune GRASP, tabu search (TS) and scatter search (SS) heuristics for the LB-ALBP and show that our procedures are able to obtain solutions of a quality that outperforms previous approaches. We rely on both s…

Project Scheduling with Stochastic Activity Interruptions

In this chapter we address the problem of scheduling the activities of a resource-constrained project, some of which may be interrupted by an uncertain amount of time. The resources may be, for example, machines in a jobshop, computers with specialized software packages (as those needed for engineering designs), or highly specialized technicians.

Advanced Scatter Search for the Max-Cut Problem

The max-cut problem consists of finding a partition of the nodes of a weighted graph into two subsets such that the sum of the weights on the arcs connecting the two subsets is maximized. This is an NP-hard problem that can also be formulated as an integer quadratic program. Several solution methods have been developed since the 1970s and applied to a variety of fields, particularly in engineering and layout design. We propose a heuristic method based on the scatter-search methodology for finding approximate solutions to this optimization problem. Our solution procedure incorporates some innovative features within the scatter-search framework: (1) the solution of the maximum diversity prob…

Reducing the bandwidth of a sparse matrix with tabu search

The bandwidth of a matrix { } ij a A = is defined as the maximum absolute difference between i and j for which 0 ≠ ij a . The problem of reducing the bandwidth of a matrix consists of finding a permutation of the rows and columns that keeps the nonzero elements in a band that is as close as possible to the main diagonal of the matrix. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the nonzero elements of the corresponding symmetrical matrix. Many bandwidth reduction algorithms have been developed since the 1960s and applied to structural engineering, fluid dynamics and network analysis. For the most part, these procedures do not incorpo…

Postoperative intestinal fistula in primary advanced ovarian cancer surgery

Antoni Llueca,1– 3 Anna Serra,1– 3 Maria Teresa Climent,1,2 Karina Maiocchi,2,4 Alvaro Villarin,2,4 Katty Delgado,2,5 Josep Mari-Alexandre,6 Juan Gilabert-Estelles,6,7 Paula Carrasco,3 Blanca Segarra,8 Luis Gomez,2,4 Juan Jose Hidalgo,3 Javier Escrig,3 Manuel Laguna2,4 On behalf of the MUAPOS working group (Multidisciplinary Unit of Abdominal Pelvic Oncology Surgery1Department of Gynecology and Obstetrics, University General Hospital of Castellon, Castellón, Spain; 2Multidisciplinary Unit of Abdominal Pelvic Oncology Surgery (MUAPOS), University General Hospital of Castellon, Castellón, Spain; 3Department of Medicine, University Jaume I (UJI), Caste…

Greedy Randomized Adaptive Search Procedures

In this chapter, we describe the process of designing heuristic procedures to solve combinatorial optimization problems.

Variable neighborhood descent for the incremental graph drawing

Abstract Graphs are used to represent reality in several areas of knowledge. Drawings of graphs have many applications, from project scheduling to software diagrams. The main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion for a good representation of a graph. In this paper we target the edge crossing reduction in the context of incremental graph drawing, in which we want to preserve the layout of a graph over successive drawings. We propose a hybrid method based on the GRASP (Greedy Randomized Adaptive Search Procedure) and VND (Variable Neighborhood Descent) methodologies and compare it with previous methods via simulation.

Connections with Other Population-Based Approaches

Throughout this book, we have established that scatter search (SS) belongs to the family of population-based metaheuristics. This family also includes the well-known evolutionary algorithms and the approach known as path relinking.

Advanced Scatter Search Designs

The preceding three tutorial chapters described somewhat basic implementations of scatter search. The purpose was to introduce basic scatter search strategies in three different problem settings. However, not all the elements implemented in the tutorial chapter can be considered basic.

The Scatter Search Methodology

Scatter search (SS) is an evolutionary approach for optimization. It has been applied to problems with continuous and discrete variables and with a single or multiple objectives. The success of SS as an optimization technique is well documented in a constantly growing number of journal articles and book chapters. This article first focuses on the basic SS framework, which is responsible for most of the outcomes reported in the literature, and then covers advanced elements that have been introduced in a few selected papers, such as the hybridization with tabu search, a well-known memory-based metaheuristic. We consider the maximum diversity problem to illustrate the search elements, methods …

Neural network prediction in a system for optimizing simulations

Neural networks have been widely used for both prediction and classification. Back-propagation is commonly used for training neural networks, although the limitations associated with this technique are well documented. Global search techniques such as simulated annealing, genetic algorithms and tabu search have also been used for this purpose. The developers of these training methods, however, have focused on accuracy rather than training speed in order to assess the merit of new proposals. While speed is not important in settings where training can be done off-line, the situation changes when the neural network must be trained and used on-line. This is the situation when a neural network i…

Pseudo-Cut Strategies for Global Optimization

Motivated by the successful use of a pseudo-cut strategy within the setting of constrained nonlinear and nonconvex optimization in Lasdon et al. (2010), we propose a framework for general pseudo-cut strategies in global optimization that provides a broader and more comprehensive range of methods. The fundamental idea is to introduce linear cutting planes that provide temporary, possibly invalid, restrictions on the space of feasible solutions, as proposed in the setting of the tabu search metaheuristic in Glover (1989), in order to guide a solution process toward a global optimum, where the cutting planes can be discarded and replaced by others as the process continues. These strategies can…

Experiences and Future Directions

The development and implementation of metaheuristic procedures usually entails a fair amount of experimentation and reliance on past experiences.

Scatter Search vs. Genetic Algorithms

The purpose of this work is to compare the performance of a scatter search (SS) implementation and an implementation of a genetic algorithm (GA) in the context of searching for optimal solutions to permutation problems. Scatter search and genetic algorithms are members of the evolutionary computation family. That is, they are both based on maintaining a population of solutions for the purpose of generating new trial solutions. Our computational experiments with four well-known permutation problems reveal that in general a GA with local search outperforms one without it. Using the same problem instances, we observed that our specific scatter search implementation found solutions of a higher …

General Concepts in Metaheuristic Search

Metaheuristics have become a very popular family of solution methods for optimization problems because they are capable of finding “acceptable” solutions in a “reasonable” amount of time. Most optimization problems in practice are too complex to be approached by exact methods that can guarantee finding global optimal solutions. The time required to find and verify globally optimal solutions is impractical in most applications. An entire computational theory, which we will not discussed here, has been developed around problem complexity. It suffices to say that it is now known that the great majority of the optimization problems found in practice fall within a category that makes them “compu…