Hybrid extreme point tabu search

We develop a new hybrid tabu search method for optimizing a continuous differentiable function over the extreme points of a polyhedron. The method combines extreme point tabu search (EPTS) with traditional descent algorithms based on linear programming. The tabu search algorithm utilizes both recenc...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 1998-04, Vol.106 (2), p.676-688
Main Authors: Blue, Jennifer A., Bennett, Kristin P.
Format: Article
Language:English
Subjects:
Algorithms
Bilinear programming
Classification
Global optimization
Job shops
Linear programming
Machine learning
Operations research
Optimization
Studies
Tabu search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We develop a new hybrid tabu search method for optimizing a continuous differentiable function over the extreme points of a polyhedron. The method combines extreme point tabu search (EPTS) with traditional descent algorithms based on linear programming. The tabu search algorithm utilizes both recency-based and frequency-based memory and oscillates between local improvement and diversification phases. The hybrid algorithm iterates between using a descent algorithm to find a local minimum and tabu search to improve locally and then move to a new area of the search space. The descent algorithm acts as a form of intensification within the tabu search. This algorithm can be used on many important classes of problems in global optimization including bilinear programming, multilinear programming, multiplicative programming, concave minimization, and complementarity problems. The algorithm is applied to two practical problems: the quasistatie multi-rigid-body contact problem (QCP) in robotics and the global tree optimization (GTO) problem in machine learning. We perform computational experiments on problems of significant real world dimensions: the smallest machine learning problem tested has on the order of 10485 extreme points. The results show our method obtains high quality solutions both by comparison with the embedded descent algorithm and by comparison to a version of tabu search that does not make use of descent.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(97)00297-X