A variable depth search algorithm with branching search for the generalized assignment problem

作     者：Yagiura, M Yamaguchi, T Ibaraki, T 

作者机构：Kyoto Univ Grad Sch Informat Dept Appl Math Kyoto 6068501 Japan 

出 版 物：《OPTIMIZATION METHODS & SOFTWARE》 (最优化方法与软件)

年 卷 期：1998年第10卷第2期

页      面：419-441页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0701[理学-数学] 

主　　题：adaptive neighborhood branching search generalized assignment problem local search metaheuristics variable depth search procedure 

摘      要：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 (M. Yagiura, T. Yamaguchi and T. Ibaraki, A variable depth sl:arch algorithm for the generalized assignment problem, Proc. 2nd Metaheuristics international Conference (MIC97), (1997) 129-130 (full version is to appear in the post-conference book)), 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.