3e cycle romand de Recherche Opérationnelle
March 7-11, 1999 Hotel Primerose, Lac-Noir (FR), Switzerland
Spring seminar / Séminaire de printemps
Invited lecturers :
Martin Grötschel
Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) and TUB (Germany)
Modern Challenges of Combinatorial OptimizationManuel Laguna
University of Colorado (USA)
An Exploration of Metaheuristic Optimization: Tabu Search, Scatter Search and Path RelinkingJon Lee
University of Kentucky (USA) and C.O.R.E. (Louvain, Belgium)
Linearization of Products
Registration :
Deadline :
January 31, 2000
Talk abstracts :
Modern Challenges of Combinatorial Optimization
Martin Grötschel
Modern mathematics appears as a key technology to solve urgent problems in many industrial growth branches. In particular optimization plays an increasingly important part therein. This will be illustrated in this series of presentations on the example of combinatorial optimization.
Important application areas will be introduced, such as
The course will describe these problem domains and the corresponding mathematical models. Main topics of the course will be the mathematical theories underlying the methods to solve these problems:
Throughout the course, particular attention will be given to present efficient algorithms to solve the applied problems.
An
Exploration of Metaheuristic Optimization:
Tabu Search, Scatter Search and Path Relinking
Manuel Laguna
These series of presentations start with the exploration of the meta-heuristic approach called tabu search, which is dramatically changing our ability to solve a host of problems in applied science, business and engineering. Tabu search has important links to evolutionary and "genetic" methods, often overlooked, through its intimate connection with scatter search and path relinking evolutionary procedures that have recently attracted attention for their ability to facilitate the solution of complex problems. The adaptive memory designs of tabu search have also provided useful alternatives and supplements to the types of memory embodied in other metaheuristic approaches such a ant systems, simulated annealing and genetic algorithms.
We then explore the evolutionary approach called scatter search, which originated from strategies for creating composite decision rules and surrogate constraints. Recent studies have demonstrated the practical advantages of this approach for solving a diverse array of optimization problems from both classical and real world settings. Scatter search contrasts with other evolutionary procedures, such as genetic algorithms, by providing unifying principles for joining solutions based on generalized path constructions in Euclidean space and by utilizing strategic designs where other approaches resort to randomization. Additional advantages are provided by intensification and diversification mechanisms that exploit adaptive memory, drawing on foundations that link scatter search to tabu search. The main goal of this exploration is to show the development of a scatter search procedure by demonstrating how it may be applied to a class of non-linear optimization problems on bounded variables and also binary optimization problems.
Our series of presentations conclude with a discussion of the scatter search generalization called path relinking. Features that have been added to scatter search by extension of its basic philosophy, are captured in the path relinking framework. From a spatial orientation, the process of generating linear combinations of a set of reference solutions (as typically done in scatter search) may be characterized as generating paths between and beyond these solutions, where solutions on such paths also serve as sources for generating additional paths. This leads to a broader conception of the meaning of creating combinations of solutions. By natural extension, such combinations may be conceived to arise by generating paths between and beyond selected solutions in neighborhood space, rather than in Euclidean space.
Finally, we highlight key ideas and research issues associated with tabu search, scatter search and path relinking that offer promise of yielding future advances.
Jon Lee
First, I will describe some joint work with D. Coppersmith and J. Leung concerning polyhderal integer linear programming methods for working with a product of (nonnegative) linear functions in 0/1 variables. One application is for modeling products of (nonnegative) integers.
Then I will discuss some related results concerning divisibility.