A Variable Depth Search Algorithm with Branching Search
for the Generalized Assignment Problem
Mutsunori Yagiura, Takashi Yamaguchi and Toshihide Ibaraki
In this paper,
we propose a variable depth search (VDS) algorithm
for the generalized assignment problem (GAP),
which is one of the representative combinatorial optimization problems,
and is known to be NP-hard.
The VDS is a generalization of the local search.
The main idea of VDS is to change the size of the neighborhood
adaptively so that the algorithm can effectively traverse larger
search space within reasonable computational time.
In our previous paper,
we proposed a simple VDS algorithm for the GAP,
and obtained good results.
To further improve the performance of the VDS,
we examine the effectiveness of incorporating branching search processes
to construct the neighborhoods.
Various types of branching rules are examined,
and it is observed that appropriate choices of branching strategies
improve the performance of VDS.
Comparisons with other existing heuristics
are also conducted using benchmark instances.
The proposed algorithm is found to be quite effective.
adaptive neighborhood, branching search,
generalized assignment problem,
local search, metaheuristics, variable depth search procedure
Optimization Methods and Software
(Special Issue Celebrating the 65th Birthday of Professor Masao Iri),
Vol. 10, No. 2 (December, 1998) pp. 419-441.
Back to the Paper List