Lagrangean Tabu Search

Tabu Search (TS) and Lagrangean relaxation (LR) are important techniques for solving large-scale combinatorial optimization problems. They have been applied successfully to a wide range of different problems from such diverse areas as routing and scheduling, network design, cutting and packing, production planning etc. In this paper we will outline how these techniques can be combined in order to obtain an even better performance. The basic idea behind such a combination is to identify promising neighbors of a current solution in the TS framework by LR. This gives a dual price and memory controlled search procedure. The principles and results of this algorithmic framework are illustrated by applying them to the solution of the capacitated warehouse location problem.