TABU SEARCH
Outline
Introduction TO TS
Parameters of Tabu Search
Basic Concepts of Tabu Search
TS vs Other Meta-heuristics
Memory in TS
Use of memory in TS
Tabus
Aspiration
Basic Tabu Search Algorithm
Stopping Conditions
Search Process – 1
Search Process – 2
Flowchart of a Standard Tabu Search Algorithm
Example
References
outline
Introduction
Tabu Search
Basic Approach – 1
Basic Approach – 2
The TS framework for multi-dimensional bin packing
Search METHODS
Computational tests – Dataset
Computational tests
Sample of results
Conclusions

Search Process – 2
Allowing infeasible solution
Constraints defining the search space can lead the process to mediocre solutions
Induces diversification
By dropping some constraints (relaxation) a larger space can be explored
Penalize objective for the violation
A well known technique: Strategic oscillation
Surrogate objective
Evaluates neighbors using a simpler function than the objective in order to spot promising candidates. (Intensification)
Auxiliary objective
Objective function can’t drive the search to more interesting areas
Orient the search by measuring desirable attributes of solutions