Tutorial 5

Memory and Evolution: Recent Advances in Metaheuristics Optimization

Dr. César Rego

E-mail: crego@bus.olemiss.edu

Dr César Rego is Associate Professor of Management Information Systems and Operations Management at the School of Business of the University of Mississippi (http://faculty.bus.olemiss.edu/crego). He received a degree in Computer Science and Applied Mathematics from the Portucalense University in Portugal. a MSc in Operations Research and Systems Engineering from the School of Engineering and Technology (IST) of the University of Lisbon, and a Ph.D. in Computer Science from the University of Versailles and INRIA - France.

He has held faculty posts in the Portucalense University and the Faculty of Sciences of the University of Lisbon, and has served as an invited professor in the IST. He has conducted research in the Operations Research Center (CIO), the Centre for Urban and Regional Systems (CESUR) of the University of Lisbon, and in the Hearin Center for Enterprise Science of the University of Mississippi.

Dr. Rego's publications have appeared in books on metaheuristics and in leading journals on optimization such as the European Journal of Operational Research (EJOR), the Journal of the Operational Research Society (JORS), Parallel Computing, Journal of Applied Mathematics and Decision Sciences, Computers & OR, Annals of Operations Research, OR Spectrum, and Management Science. In the practical realm, he has designed and implemented computer software for solving real-world problems for several major companies.

During the last four years he has been serving as principal investigator and co-investigator in six major research grants from the U.S. Navy Office of Naval Research (ONR) with total funding exceeding 2 million dollars.

Dr. Rego is Associate Editor of the journal Operational Research: An International Journal, Hellenic Operational Research Society, the Journal of Heuristics, Kluwer Academic Publishers, and editor of the book Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search, Kluwer Academic Publishers. He has served on several scientific committees such as a review panel for the National Science Foundation (NSF) and examiner of several doctoral dissertations in Europe, USA and Canada.

Dr. Rego has organized and chaired numerous sessions and clusters in international conferences and has served as invited speaker in a number plenary sessions. He is the chair of the EU/ME Special Interest Group on Tabu Search and Scatter Search, in the European Chapter on Metaheuristics of EURO. He is a member of APDIO and INFORMS, a Research Associate of the Center for Research on Transportation (CRT) - Montreal, Canada, and a Senior Research Consultant for OptTek Systems, Inc.


Adaptive memory programming (AMP) has been the source of numerous important developments in metaheuristics throughout the last decade. The term refers to the appropriate integration of memory structures to permit search algorithm for optimization problems to explore the solution space effectively.

Because AMP is the foundation of tabu search (TS), which appeared as the first method specially designed to exploit adaptive memory, the terms TS and AMP have often been used interchangeably. However, more recently the principles of AMP have likewise been used to enhance other approaches as in the creation of hybrid algorithms that incorporate tabu search components. Many important examples exist of methods that integrate genetic algorithms and evolutionary computation methods with adaptive memory, but perhaps the most prominent examples that successfully use adaptive memory outside of tabu search are the recent developments in scatter search and its generalization, the path-relinking approach, whose origins share overlaps with tabu search.

On the other hand, relaxation techniques have been widely used in combinatorial optimization to provide bounds for tree search procedures (such as branch and bound) as well as to produce heuristic algorithms. These techniques are based on solving an auxiliary (or relaxed) problem derived from the original by dropping or diminishing the restrictiveness of some constraints. Relaxation Adaptive Memory Programming (RAMP) is a new metaheuristic that integrates these two key developments by proposing a unified framework for the design of dual and primal-dual metaheuristics that take full advantage of adaptive memory programming.

The purpose of this tutorial is to introduce fundamental principles of mathematical relaxation and adaptive memory programming, as embedded in state-of-the-art algorithms that are yielding new advances in the field of metaheuristics. The practical significance of this work is demonstrated by the ability to solve challenging problems more effectively, over domains that include facility location, routing and distribution, production scheduling, resource allocation, manpower planning, data mining, classification and computational biology, just to cite a few.


Illustrate the principles of mathematical relaxation, local search and metaheuristics, and discuss major optimization techniques that make effective use of these concepts with special emphasis to those that rely upon adaptive memory programming..

Duration: 3.00 HR


1. Fundamentals of Mathematical Relaxation

Linear Programming Relaxation
Lagrangean Relaxation
Surrogate Constraint Relaxation
Cross-Parametric Relaxation

2. Local Search and Adaptive Memory Programming

Local Search
Tabu Search
Scatter Search

3. Advanced Neighborhood Constructions

Ejection Chain Methods
Adaptive Tree Search Neighborhoods

4. Applications: Illustrative examples

Routing and Distribution
Network Design
Facility Location
Computational Biology

Target Audience:

Professionals working in areas of decision systems and operations management
Researchers working in areas of management science, operations management and engineering
Students in areas of business, operations research, mathematics, computer science and engineering


Basic concepts of optimization