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…

Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization

We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of high-quality solutions throughout the search. After a fixed number of GRASP iterations, exterior path relinking is applied between all pairs of elite set solutions and the best solution found is returned. Exterior path relinking, or path separation, a variant of the more common interior path relinking, is first applied in this paper. In interior path relinking, paths in the neighborhood solution space connecting good solutions are explored betwe…

Multilayer neural networks: an experimental evaluation of on-line training methods

Artificial neural networks (ANN) are inspired by the structure of biological neural networks and their ability to integrate knowledge and learning. In ANN training, the objective is to minimize the error over the training set. The most popular method for training these networks is back propagation, a gradient descent technique. Other non-linear optimization methods such as conjugate directions set or conjugate gradient have also been used for this purpose. Recently, metaheuristics such as simulated annealing, genetic algorithms or tabu search have been also adapted to this context.There are situations in which the necessary training data are being generated in real time and, an extensive tr…

GRASP and path relinking for the equitable dispersion problem

The equitable dispersion problem consists in selecting a subset of elements from a given set in such a way that a measure of dispersion is maximized. In particular, we target the Max-Mean dispersion model in which the average distance between the selected elements is maximized. We first review previous methods and mathematical formulations for this and related dispersion problems and then propose a GRASP with a Path Relinking in which the local search is based on the Variable Neighborhood methodology. Our method is specially suited for instances in which the distances represent affinity and are not restricted to take non-negative values. The computational experience with 120 instances shows…

Intelligent Multi-Start Methods

Heuristic search procedures aimed at finding globally optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored, which constitutes a multi-start procedure. In this chapter we describe the best known multi-start methods for solving optimization problems. We also describe their connections with other metaheuristic methodologies. We propose classifying these methods in terms of their use of randomization, memory and degree of rebuild. We also present a computational comparison of these methods on solvi…

Scatter Search and Path-Relinking: Fundamentals, Advances, and Applications

Scatter search is an evolutionary metaheuristic that explores solution spaces by evolving a set of reference points, operating on a small set of solutions while making only limited use of randomization. We give a comprehensive description of the elements and methods that make up its template, including the most recent elements incorporated in successful applications in both global and combinatorial optimization. Path-relinking is an intensification strategy to explore trajectories connecting elite solutions obtained by heuristic methods such as scatter search, tabu search, and GRASP. We describe its mechanics, implementation issues, randomization, the use of pools of high-quality solutions …

Heuristics for the capacitated modular hub location problem

Abstract In this paper we study the hub location problem, where the goal is to identify an optimal subset of facilities (hubs) to minimize the transportation cost while satisfying certain capacity constraints. In particular, we target the single assignment version, in which each node in the transportation network is assigned to only one hub to route its traffic. We consider here a realistic variant introduced previously, in which the capacity of edges between hubs is increased in a modular way. This reflects the practical situation in air traffic where the number of flights between two locations implies a capacity in terms of number of passengers. Then, the capacity can be increased in a mo…

Path relinking and GRG for artificial neural networks

Artificial neural networks (ANN) have been widely used for both classification and prediction. This paper is focused on the prediction problem in which an unknown function is approximated. ANNs can be viewed as models of real systems, built by tuning parameters known as weights. In training the net, the problem is to find the weights that optimize its performance (i.e., to minimize the error over the training set). Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been successfully applied to solve this problem. In this paper we propose a path relinking implementation to solve the neural ne…

Heuristics for the Mixed Rural Postman Problem

Abstract The Rural Postman Problem on a mixed graph (MRPP) consists of finding a minimum cost tour which traverses, at least once, the arcs and edges of a given subset of the arcs and edges of the graph. This problem is known to be NP-hard. This paper presents two heuristic approaches to solve it. An approximate algorithm based on the resolution of some flow and matching problems and a tabu search implementation is presented. The tabu search algorithm seeks high-quality tours by means of a switching mechanism in an intensification phase and two levels of diversification. Computational results are presented to assess the merits of the method. Scope and purpose Routing Problems arise in sever…

Branch and bound for the cutwidth minimization problem

The cutwidth minimization problem consists of finding a linear arrangement of the vertices of a graph where the maximum number of cuts between the edges of the graph and a line separating consecutive vertices is minimized. We first review previous approaches for special classes of graphs, followed by lower bounds and then a linear integer formulation for the general problem. We then propose a branch-and-bound algorithm based on different lower bounds on the cutwidth of partial solutions. Additionally, we introduce a Greedy Randomized Adaptive Search Procedure (GRASP) heuristic to obtain good initial solutions. The combination of the branch-and-bound and GRASP methods results in optimal solu…

Variable Neighborhood Search for the Vertex Separation Problem

The vertex separation problem belongs to a family of optimization problems in which the objective is to nd the best separator of vertices or edges in a generic graph. This optimization problem is strongly related to other well-known graph problems; such as the Path-Width, the Node Search Number or the Interval Thickness, among others. All of these optimization problems are NP-hard and have practical applications in VLSI, computer language compiler design or graph drawing. Up to know, they have been generally tackled with exact approaches, presenting polynomial-time algorithms to obtain the optimal solution for speci c types of graphs. However, in spite of their practical applications, these…

The Rural Postman Problem on mixed graphs with turn penalties

In this paper we deal with a problem which generalizes the Rural Postman Problem defined on a mixed graph (MRPP). The generalization consists of associating a non-negative penalty to every turn as well as considering the existence of forbidden turns. This new problem fits real-world situations more closely than other simpler problems. A solution tour must traverse all the requiring service arcs and edges of the graph while not making forbidden turns. Its total cost will be the sum of the costs of the traversed arcs and edges together with the penalties associated with the turns done. The Mixed Rural Postman Problem with Turn Penalties (MRPPTP) consists of finding such a tour with a total mi…

Randomized heuristics for the Capacitated Clustering Problem

In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between randomization and greediness on the performance of these multi-start heuristic search methods when solving this NP-hard problem. The former is a memory-less approach that constructs independent solutions, while the latter is a memory-based method that constructs linked solutions, obtained by partially rebuilding previous ones. Both are based on the combination of greediness and randomization in the constructive process, and coupled with a subsequent l…

Scatter search for an uncapacitated p-hub median problem

Scatter search is a population-based method that has been shown to yield high-quality outcomes for combinatorial optimization problems. It uses strategies for combining solution vectors that have proved effective in a variety of problem settings. In this paper, we present a scatter search implementation for an NP -hard variant of the classic p-hub median problem. Specifically, we tackle the uncapacitated r-allocation p-hub median problem, which consists of minimizing the cost of transporting the traffics between nodes of a network through special facilities that act as transshipment points. This problem has a significant number of applications in practice, such as the design of transportati…

GRASP with path relinking heuristics for the antibandwidth problem

This article proposes a linear integer programming formulation and several heuristics based on GRASP and path relinking for the antibandwidth problem. In the antibandwidth problem, one is given an undirected graph with n nodes and must label the nodes in a way that each node receives a unique label from the set {1, 2,…,n}, such that, among all adjacent node pairs, the minimum difference between the node labels is maximized. Computational results show that only small instances of this problem can be solved exactly (to optimality) with a commercial integer programming solver and that the heuristics find high-quality solutions in much less time than the commercial solver. © 2010 Wiley Periodic…

Erratum to: Scatter Search – Methodology and Implementations in C

Tabu search for min-max edge crossing in graphs

Abstract Graph drawing is a key issue in the field of data analysis, given the ever-growing amount of information available today that require the use of automatic tools to represent it. Graph Drawing Problems (GDP) are hard combinatorial problems whose applications have been widely relevant in fields such as social network analysis and project management. While classically in GDPs the main aesthetic concern is related to the minimization of the total sum of crossing in the graph (min-sum), in this paper we focus on a particular variant of the problem, the Min-Max GDP, consisting in the minimization of the maximum crossing among all egdes. Recently proposed in scientific literature, the Min…

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…

Use of Memory in Scatter Search

Arc crossing minimization in graphs with GRASP

Graphs are commonly used to represent information in many fields of science and engineering. Automatic drawing tools generate comprehensible graphs from data, taking into account a variety of properties, enabling users to see important relationships in the data. The goal of limiting the number of arc crossings is a well-admitted criterion for a good drawing. In this paper, we present a Greedy Randomized Adaptive Search Procedure (GRASP) for the problem of minimizing arc crossings in graphs. Computational experiments with 200 graphs with up to 350 vertices are presented to assess the merit of the method. We show that simple heuristics are very fast but result in inferior solutions, while hig…

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.

Multi-start methods for combinatorial optimization

Abstract Multi-start methods strategically sample the solution space of an optimization problem. The most successful of these methods have two phases that are alternated for a certain number of global iterations. The first phase generates a solution and the second seeks to improve the outcome. Each global iteration produces a solution that is typically a local optimum, and the best overall solution is the output of the algorithm. The interaction between the two phases creates a balance between search diversification (structural variation) and search intensification (improvement), to yield an effective means for generating high-quality solutions. This survey briefly sketches historical devel…

Variable neighborhood search for the linear ordering problem

Given a matrix of weights, the linear ordering problem (LOP) consists of finding a permutation of the columns and rows in order to maximize the sum of the weights in the upper triangle. This NP-complete problem can also be formulated in terms of graphs, as finding an acyclic tournament with a maximal sum of arc weights in a complete weighted graph. In this paper, we first review the previous methods for the LOP and then propose a heuristic algorithm based on the variable neighborhood search (VNS) methodology. The method combines different neighborhoods for an efficient exploration of the search space. We explore different search strategies and propose a hybrid method in which the VNS is cou…

Heuristics for the min–max arc crossing problem in graphs

Abstract In this paper, we study the visualization of complex structures in the context of automatic graph drawing. Constructing geometric representations of combinatorial structures, such as networks or graphs, is a difficult task that requires an expert system. The automatic generation of drawings of graphs finds many applications from software engineering to social media. The objective of graph drawing expert systems is to generate layouts that are easy to read and understand. This main objective is achieved by solving several optimization problems. In this paper we focus on the most important one: reducing the number of arc crossings in the graph. This hard optimization problem has been…

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…

Adaptive memory programing for the robust capacitated international sourcing problem

The International Sourcing Problem consists of selecting a subset from an available set of potential suppliers internationally located. The selected suppliers must meet the demand for items from a set of plants, which are also located worldwide. Since the costs are affected by macroeconomic conditions in the countries where the supplier and the plant are located, the formulation considers the uncertainty associated with changes in these conditions. We formulate the robust capacitated international sourcing problem by means of a scenario-optimization approach. When dealing with uncertainty, one of the most common approaches in the literature is to formulate the problem via a set of possible …

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…

A tabu search algorithm for the bipartite drawing problem

Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present a Tabu Search (TS) scheme for the BDP. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 300 randomly generated test problems. The two algorithms have been compared with the best heuristics…

Commercial Scatter Search Implementation

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

A strategic oscillation simheuristic for the Time Capacitated Arc Routing Problem with stochastic demands

Abstract The Time Capacitated Arc Routing Problem (TCARP) extends the classical Capacitated Arc Routing Problem by considering time-based capacities instead of traditional loading capacities. In the TCARP, the costs associated with traversing and servicing arcs, as well as the vehicle’s capacity, are measured in time units. The increasing use of electric vehicles and unmanned aerial vehicles, which use batteries of limited duration, illustrates the importance of time-capacitated routing problems. In this paper, we consider the TCARP with stochastic demands, i.e.: the actual demands on each edge are random variables which specific values are only revealed once the vehicle traverses the arc. …

A branch and bound algorithm for the maximum diversity problem

This article begins with a review of previously proposed integer formulations for the maximum diversity problem (MDP). This problem consists of selecting a subset of elements from a larger set in such a way that the sum of the distances between the chosen elements is maximized. We propose a branch and bound algorithm and develop several upper bounds on the objective function values of partial solutions to the MDP. Empirical results with a collection of previously reported instances indicate that the proposed algorithm is able to solve all the medium-sized instances (with 50 elements) as well as some large-sized instances (with 100 elements). We compare our method with the best previous line…

Branch-and-Bound

We now turn to the discussion of how to solve the linear ordering problem to (proven) optimality. In this chapter we start with the branch-and-bound method which is a general procedure for solving combinatorial optimization problems. In the subsequent chapters this approach will be realized in a special way leading to the so-called branch-and-cut method. There are further possibilities for solving the LOP exactly, e.g. by formulating it as dynamic program or as quadratic assignment problem, but these approaches did not lead to the implementation of practical algorithms and we will not elaborate on them here.

A parallel variable neighborhood search approach for the obnoxious p -median problem

Metaheuristics for the linear ordering problem with cumulative costs

The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The compa…

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.

GRASP with path relinking for the orienteering problem

In this paper, we address an optimization problem resulting from the combination of the well-known travelling salesman and knapsack problems. In particular, we target the orienteering problem, originated in the context of sport, which consists of maximizing the total score associated with the vertices visited in a path within the available time. The problem, also known as the selective travelling salesman problem, is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in routing and tourism. We propose a heuristic method—based on the Greedy Randomized Adapt…

Artificial Neural Networks for Prediction

The design and implementation of intelligent systems with human capabilities is the starting point to design Artificial Neural Networks (ANNs). The original idea takes after neuroscience theory on how neurons in the human brain cooperate to learn from a set of input signals to produce an answer. Because the power of the brain comes from the number of neurons and the multiple connections between them, the basic idea is that connecting a large number of simple elements in a specific way can form an intelligent system.

Scatter Search—Wellsprings and Challenges

I came up with the idea of editing this volume in the summer of 2002 while working on the book "Scatter search methodologies and implementations in C" with Manuel Laguna in the University of Colorado at Boulder. There, Fred Glover kindly let me use his office, where I found a copy of the "Tabu Search Methods for Optimization" special issue that he edited in 1988 for the European Journal of Operational Research. This encounter made me realize that Scatter Search has reached a level of maturity as an optimization method that has parallels with what Tabu Search was experiencing in the late eighties. So I thought that the moment was perfect to embark on this project, which has been supported en…

Scatter Search for the Point-Matching Problem in 3D Image Registration

Scatter search 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, such as the surrogate constraint method, scatter search uses strategies for combining solution vectors that have proved effective in a variety of problem settings. We present a scatter-search implementation designed to find high-quality solutions for the 3D image-registration problem, which has many practical applications. This problem arises in computer vision applications when finding a correspondence or transformation …

Measuring diversity. A review and an empirical analysis

Abstract Maximum diversity problems arise in many practical settings from facility location to social networks, and constitute an important class of NP-hard problems in combinatorial optimization. There has been a growing interest in these problems in recent years, and different mathematical programming models have been proposed to capture the notion of diversity. They basically consist of selecting a subset of elements of a given set in such a way that a measure based on their pairwise distances is maximized to achieve dispersion or representativeness. In this paper, we perform an exhaustive comparison of four mathematical models to achieve diversity over the public domain library MDPLIB, …

Iterated greedy with variable neighborhood search for a multiobjective waste collection problem

Abstract In the last few years, the application of decision making to logistic problems has become crucial for public and private organizations. Efficient decisions clearly contribute to improve operational aspects such as cost reduction or service improvement. The particular case of waste collection service considered in this paper involves a set of economic, labor and environmental issues that translate into difficult operational problems. They pose a challenge to nowadays optimization technologies since they have multiple constraints and multiple objectives that may be in conflict. We therefore need to resort to multiobjective approaches to model and solve this problem, providing efficie…

Tabu search for a multi-objective routing problem

Multi-objective optimization problems deal with the presence of different conflicting objectives. Given that it is not possible to obtain a single solution by optimizing all the objectives simultaneously, a common way to face these problems is to obtain a set of efficient solutions called the non-dominated frontier. In this paper, we address the problem of routing school buses with two objectives: minimize the number of buses, and minimize the longest time a student would have to stay in the bus. The trade-off in this problem is between service level, which is represented by the maximum route length, and operational cost, which is represented by the number of buses in the solution. We prese…

Heuristics for the Constrained Incremental Graph Drawing Problem

Abstract Visualization of information is a relevant topic in Computer Science, where graphs have become a standard representation model, and graph drawing is now a well-established area. Within this context, edge crossing minimization is a widely studied problem given its importance in obtaining readable representations of graphs. In this paper, we focus on the so-called incremental graph drawing problem, in which we try to preserve the user’s mental map when obtaining successive drawings of the same graph. In particular, we minimize the number of edge crossings while satisfying some constraints required to preserve the position of vertices with respect to previous drawings. We propose heur…

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.

Solving dynamic memory allocation problems in embedded systems with parallel variable neighborhood search strategies

International audience; Embedded systems have become an essential part of our lives, thanks to their evolution in the recent years, but the main drawback is their power consumption. This paper is focused on improving the memory allocation of embedded systems to reduce their power consumption. We propose a parallel variable neighborhood search algorithm for the dynamic memory allocation problem, and compare it with the state of the art. Computational results and statistical tests applied show that the proposed algorithm produces significantly better outcomes than the previous algorithm in shorter computing time.

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.

An Aggressive Search Procedure for the Bipartite Drawing Problem

Graphs are used to represent reality in several areas of knowledge. This has generated considerable interest in graph drawing algorithms. Arc crossing minimization is a fundamental aesthetic criterion to obtain a readable map of a graph. The problem of minimizing the number of arc crossings in a bipartite graph (BDP) is NP-complete. In this paper we present an aggressive search scheme for the BDP based on the Intensification, Diversification and Strategic Oscillation elements of Tabu Search. Several algorithms can be obtained with this scheme by implementing different evaluators in the move definitions. In this paper we propose two variants. Computational results are reported on a set of 30…

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…

GRASP and path relinking for the max–min diversity problem

The max-min diversity problem (MMDP) consists in selecting a subset of elements from a given set in such a way that the diversity among the selected elements is maximized. The problem is NP-hard and can be formulated as an integer linear program. Since the 1980s, several solution methods for this problem have been developed and applied to a variety of fields, particularly in the social and biological sciences. We propose a heuristic method-based on the GRASP and path relinking methodologies-for finding approximate solutions to this optimization problem. We explore different ways to hybridize GRASP and path relinking, including the recently proposed variant known as GRASP with evolutionary p…

A GRASP heuristic for the mixed Chinese postman problem

Abstract Arc routing problems (ARPs) consist of finding a traversal on a graph satisfying some conditions related to the links of the graph. In the Chinese postman problem (CPP) the aim is to find a minimum cost tour (closed walk) traversing all the links of the graph at least once. Both the Undirected CPP, where all the links are edges that can be traversed in both ways, and the Directed CPP, where all the links are arcs that must be traversed in a specified way, are known to be polynomially solvable. However, if we deal with a mixed graph (having edges and arcs), the problem turns out to be NP -hard. In this paper, we present a heuristic algorithm for this problem, the so-called Mixed CPP…

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naive ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for…

GRASP and path relinking for the matrix bandwidth minimization

In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the nonzero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a Path Relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with Path Relinking is also found to be competitive with a recently published tabu search algorithm that is considered one of the best currently available for band…

Heuristics for the bi-objective path dissimilarity problem

In this paper the path dissimilarity problem is considered. The problem has previously been studied within several contexts, the most popular of which is motivated by the need to select transportation routes for hazardous materials. The aim of this paper is to formally introduce the problem as a bi-objective optimization problem, in which a single solution consists of a set of p different paths, and two conflicting objectives arise, on one hand the average length of the paths must be kept low, and on the other hand the dissimilarity among the paths in the set should be kept high. Previous methods are reviewed and adapted to this bi-objective problem, thus we can compare the methods using th…

Improved heuristics for the regenerator location problem

Telecommunication systems use optical signals to transmit information. The strength of a signal in an optical network deteriorates and loses power as it goes farther from the source, mainly due to attenuation. Therefore, to enable the signal to arrive its intended destination with good quality, it is necessary to regenerate the signal periodically using regenerators. These components are relatively expensive and therefore it is desirable to deploy as few of them as possible in the network. In the regenerator location problem (RLP), we are given an undirected graph, positive edge lengths, and a parameter specifying the maximum length that a signal can travel before its quality deteriorates a…

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…

Tabu search for the dynamic Bipartite Drawing Problem

Abstract Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically…

Special issue of Computers and Operations Research: GRASP with Path Relinking: Developments and applications

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.

GRASP with exterior path-relinking and restricted local search for the multidimensional two-way number partitioning problem

In this work, we tackle multidimensional two-way number partitioning (MDTWNP) problem by combining GRASP with Exterior Path Relinking. In the last few years, the combination of GRASP with path relinking (PR) has emerged as a highly effective tool for finding high-quality solutions for several difficult problems in reasonable computational time. However, in most of the cases, this hybridisation is limited to the variant known as interior PR. Here, we couple GRASP with the "exterior form" of path relinking and perform extensive experimentation to evaluate this variant. In addition, we enhance our GRASP with PR method with a novel local search method specially designed for the MDTWNP problem. …

A review on discrete diversity and dispersion maximization from an OR perspective

Abstract The problem of maximizing diversity or dispersion deals with selecting a subset of elements from a given set in such a way that the distance among the selected elements is maximized. The definition of distance between elements is customized to specific applications, and the way that the overall diversity of the selected elements is computed results in different mathematical models. Maximizing diversity by means of combinatorial optimization models has gained prominence in Operations Research (OR) over the last two decades, and constitutes nowadays an important area. In this paper, we review the milestones in the development of this area, starting in the late eighties when the first…

Black-Box solvers in combinatorial optimization

Black box optimizers have a long tradition in the field of operations research. These procedures treat the objective function evaluation as a black box and therefore do not take advantage of its specific structure. Black-box optimization refers to the process in which there is a complete separation between the evaluation of the objective function —and perhaps other functions used to enforce constraints— and the solution procedure. The challenge of optimizing black boxes is to develop methods that can produce outcomes of reasonable quality without taking advantage of problem structure and employing a computational effort that is adequate for the context.

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…

Heuristic Solutions for a Class of Stochastic Uncapacitated p-Hub Median Problems

In this work, we propose a heuristic procedure for a stochastic version of the uncapacitated r-allocation p-hub median problem with nonstop services. In particular, we assume that the number of hubs to which a terminal can be allocated is bounded from above by r. Additionally, we consider the possibility of shipping traffic directly between terminals (nonstop services). Uncertainty is associated with the traffic to be shipped between nodes and with the transportation costs. If we assume that such uncertainty can be captured by a finite set of scenarios, each of which with a probability known in advance, it is possible to develop a compact formulation for the deterministic equivalent proble…

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…

Adaptive memory programming for the dynamic bipartite drawing problem

Abstract The bipartite drawing problem is a well-known NP-hard combinatorial optimization problem with numerous applications. The aim is to minimize the number of edge crossings in a two-layer graph, in which the edges are drawn as straight lines. We consider the dynamic variant of this problem, called the dynamic bipartite drawing problem (DBDP), which consists of adding (resp. or removing) vertices and edges to (resp. or from) a given bipartite drawing, thereby obtaining a new drawing with a layout similar to that of the original drawing. To solve this problem, we propose a tabu search method that incorporates adaptive memory to search the solution space efficiently. In this study, we com…

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…

Multi-objective memetic optimization for the bi-objective obnoxious p -median problem

Abstract Location problems have been studied extensively in the optimization literature, the p-median being probably one of the most tackled models. The obnoxious p-median is an interesting variant that appears in the context of hazardous location. The aim of this paper is to formally introduce a bi-objective optimization model for this problem, in which a solution consists of a set of p locations, and two conflicting objectives arise. On the one hand, the sum of the minimum distance between each client and their nearest open facility and, on the other hand, the dispersion among facilities. Both objective values should be kept as large as possible for a convenient location of dangerous faci…

GRASP and Path Relinking for the Two-Dimensional Two-Stage Cutting-Stock Problem

We develop a greedy randomized adaptive search procedure (GRASP) for the constrained two-dimensional two-stage cutting-stock problem. This is a special cutting problem in which the cut is performed in two phases. In the first phase, the stock rectangle is slit down its width into different vertical strips and in the second phase, each of these strips is processed to obtain the final pieces. We propose two different algorithms based on GRASP methodology. One is “piece-oriented” while the other is “strip-oriented.” Both procedures are fast and provide solutions of different structures to this cutting problem. We also propose a path-relinking algorithm, which operates on a set of elite soluti…

A hybrid metaheuristic for the cyclic antibandwidth problem

We propose a hybrid artificial bee colony algorithm for the cyclic antibandwidth problem.We present a computational comparison of different parameter settings.We derive a fine-tuning hybrid artificial bee colony algorithm.The proposal is very competitive with the state-of-the-art algorithm for the cyclic antibandwidth problem. In this paper, we propose a hybrid metaheuristic algorithm to solve the cyclic antibandwidth problem. This hard optimization problem consists of embedding an n-vertex graph into the cycle Cn, such that the minimum distance (measured in the cycle) of adjacent vertices is maximized. It constitutes a natural extension of the well-known antibandwidth problem, and can be v…

A heuristic algorithm for project scheduling with splitting allowed

In this article, we analyze the precedence diagramming method, the only published algorithm for time-only project scheduling with activity splitting allowed. The criteria used in this method (forward and backward pass computations) for deciding when an activity has to be interrupted are shown to be invalid in some situations. We look into the causes of these failures and propose new formulae that always provide feasible solutions. The new algorithm has been tested on 240 randomly generated problems ranging up to 600 activities and 7,200 precedence relationships, resulting in an average deviation from optima of less than 1 percent.

Advanced Multi-start Methods

Heuristic search procedures that aspire to find globally optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory, and degree of rebuild. We also present a computational comparison of these methods on solving the maximum diversity problem in terms of solution quality and diversification power.

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…

Heuristics for the capacitated dispersion problem

Tabu and Scatter Search for Artificial Neural Networks

In this paper we address the problem of training multilayer feed-forward neural networks. These networks have been widely used for both prediction and classification in many different areas. Although the most popular method for training these networks is back propagation, other optimization methods such as tabu search or scatter search have been applied to solve this problem. This paper presents a new training algorithm based on the tabu search methodology that incorporates elements for search intensification and diversification by utilizing strategic designs where other previous approaches resort to randomization. Our method considers context and search information, as it is provided by th…

Branch-and-Cut

This chapter focuses on the approach for solving the LOP to optimality which can currently be seen as the most successful one. It is a branch-and-bound algorithm, where the upper bounds are computed using linear programming relax- ations.

Multiobjective GRASP with Path Relinking

In this paper we review and propose different adaptations of the GRASP metaheuristic to solve multiobjective combinatorial optimization problems. In particular, we describe several alternatives to specialize the construction and improvement components of GRASP when two or more objectives are considered. GRASP has been successfully coupled with Path Relinking for single-objective optimization. Moreover, we propose different hybridizations of GRASP and Path Relinking for multiobjective optimization. We apply the proposed GRASP with Path Relinking variants to two combinatorial optimization problems, the biobjective orienteering problem and the biobjective path dissimilarity problem. We report …

GRASP for the uncapacitated r-allocation p-hub median problem

In this paper we propose a heuristic for the Uncapacitated r-Allocation p-Hub Median Problem. In the classical p-hub location problem, given a set of nodes with pairwise traffic demands, we must select p of them as hub locations and route all traffics through them at a minimum cost. We target here an extension, called the r-allocation p-hub median problem, recently proposed by Yaman [19], in which every node is assigned to r of the p selected hubs (r@?p) and we are restricted to route the traffic of the nodes through their associated r hubs. As it is usual in this type of problems, our method has three phases: location, assignment and routing. Specifically, we propose a heuristic based on t…

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…

Tabu search with strategic oscillation for the quadratic minimum spanning tree

The quadratic minimum spanning tree problem consists of determining a spanning tree that minimizes the sum of costs of the edges and pairs of edges in the tree. Many algorithms and methods have been proposed for this hard combinatorial problem, including several highly sophisticated metaheuristics. This article presents a simple Tabu Search (TS) for this problem that incorporates Strategic Oscillation (SO) by alternating between constructive and destructive phases. The commonalties shared by this strategy and the more recently introduced methodology called iterated greedy search are shown and implications of their differences regarding the use of memory structures are identified. Extensive …

A Multistart Scatter Search Heuristic for Smooth NLP and MINLP Problems

The algorithm described here, called OptQuest/NLP or OQNLP, is a heuristic designed to find global optima for pure and mixed integer nonlinear problems with many constraints and variables, where all problem functions are differentiable with respect to the continuous variables. It uses OptQuest, a commercial implementation of scatter search developed by OptTek Systems, Inc., to provide starting points for a gradient-based local NLP solver. This solver seeks a local solution from a subset of these points, holding discrete variables fixed. The procedure is motivated by our desire to combine the superior accuracy and feasibility-seeking behavior of gradient-based local NLP solvers with the glob…

Greedy Randomized Adaptive Search Procedures

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

Multi-Start Methods

Heuristic search procedures that aspire to find global optimal solutions to hard combinatorial optimization problems usually require some type of diversification to overcome local optimality. One way to achieve diversification is to re-start the procedure from a new solution once a region has been explored. In this chapter we describe the best known multi-start methods for solving optimization problems. We propose classifying these methods in terms of their use of randomization, memory and degree of rebuild. We also present a computational comparison of these methods on solving the linear ordering problem in terms of solution quality and diversification power.

An evolutionary method for complex-process optimization

10 páginas, 7 figuras, 7 tablas

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…

3D inter-subject medical image registration by scatter search

Image registration is a very active research area in computer vision, namely it is used to find a transformation between two images taken under different conditions. Point matching is an image registration approach based on searching for the right pairing of points between the two images. From this matching, the registration transformation we are searching, can be inferred by means of numerical methods. In this paper, we propose a scatter search (SS) algorithm to solve the matching problem. SS is a hybrid metaheuristic with a good trade-off between search space diversification and intensification. On the one hand, diversity is basically introduced from a population-based approach where syst…

GRASP and tabu search for the generalized dispersion problem

Abstract The problem of maximizing dispersion requires the selection of a specific number of elements from a given set, in such a way that the minimum distance between the pairs of selected elements is maximized. In recent years, this problem has received a lot of attention and has been solved with many complex heuristics. However, there is a recent variant in which the selected elements have to satisfy two realistic constraints, a minimum capacity limit and a maximum budget, which in spite of its practical significance in facility location, has received little attention. In this paper, we first propose mathematical models to obtain the optimal solution of small- and medium-size instances, …

Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem

Abstract The Obnoxious p-Median problem consists in selecting a subset of p facilities from a given set of possible locations, in such a way that the sum of the distances between each customer and its nearest facility is maximized. The problem is NP -hard and can be formulated as an integer linear program. It was introduced in the 1990s, and a branch and cut method coupled with a tabu search has been recently proposed. In this paper, we propose a heuristic method – based on the Greedy Randomized Adaptive Search Procedure, GRASP, methodology – for finding approximate solutions to this optimization problem. In particular, we consider an advanced GRASP design in which a filtering mechanism avo…

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…

Tabu search for the Max–Mean Dispersion Problem

In this paper, we address a variant of a classical optimization model in the context of maximizing the diversity of a set of elements. In particular, we propose heuristics to maximize the mean dispersion of the selected elements in a given set. This NP-hard problem was recently introduced as the maximum mean dispersion problem (MaxMeanDP), and it models several real problems, from pollution control to ranking of web pages. In this paper, we first review the previous methods for the MaxMeanDP, and then explore different tabu search approaches, and their influence on the quality of the solutions obtained. As a result, we propose a dynamic tabu search algorithm, based on three different neighb…

Experiences and Future Directions

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

The Linear Ordering Polytope

So far we developed a general integer programming approach for solving the LOP. It was based on the canonical IP formulation with equations and 3-dicycle inequalities which was then strengthened by generating mod-k-inequalities as cutting planes. In this chapter we will add further ingredients by looking for problem- specific inequalities. To this end we will study the convex hull of feasible solutions of the LOP: the so-called linear ordering polytope.

Heuristics for the Bi-Objective Diversity Problem

Abstract The Max-Sum diversity and the Max-Min diversity are two well-known optimization models to capture the notion of selecting a subset of diverse points from a given set. The resolution of their associated optimization problems provides solutions of different structures, in both cases with desirable characteristics. They have been extensively studied and we can find many metaheuristic methodologies, such as Greedy Randomized Adaptive Search Procedure, Tabu Search, Iterated Greedy, Variable Neighborhood Search, and Genetic algorithms applied to them to obtain high quality solutions. In this paper we solve the bi-objective problem in which both models are simultaneously optimized. No pre…

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 …

Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization

The algorithm described here, called OptQuest/NLP or OQNLP, is a heuristic designed to find global optima for pure and mixed integer nonlinear problems with many constraints and variables, where all problem functions are differentiable with respect to the continuous variables. It uses OptQuest, a commercial implementation of scatter search developed by OptTek Systems, Inc., to provide starting points for any gradient-based local solver for nonlinear programming (NLP) problems. This solver seeks a local solution from a subset of these points, holding discrete variables fixed. The procedure is motivated by our desire to combine the superior accuracy and feasibility-seeking behavior of gradie…

Scatter Search and Path Relinking

Scatter search (SS) and path relinking (PR) are evolutionary methods that have been successfully applied to a wide range of hard optimization problems. The fundamental concepts and principles of the methods were first proposed in the 1970s and 1980s, and were based on formulations, dating back to the 1960s, for combining decision rules and problem constraints. The methods use strategies for search diversification and intensification that have proved effective in a variety of optimization problems and that have sometimes been embedded in other evolutionary methods to yield improved performance. This paper examines the scatter search and path relinking methodologies from both conceptual and p…

Heuristics for the bandwidth colouring problem

The bandwidth colouring problem consists of assigning a colour to each vertex of a graph, so that the absolute value of the difference between the colours of adjacent vertices is at least the value of the weight of the associated edge. This problem generalises the classical vertex colouring problem and different heuristics have recently been proposed to obtain high quality solutions. In this paper we describe both memory-based and memory-less methods to solve the bandwidth colouring problem. In particular we propose new constructive and improvement methods based on tabu search and GRASP. Comparison of our results with previously reported instances and existing heuristics indicate that the m…

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the propose…

Incremental bipartite drawing problem

Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…

A tabu thresholding algorithm for arc crossing minimization in bipartite graphs

Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test proble…

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…