A Novel Hyper-Heuristic with Decomposition and Mathematical Programming

Zongzheng Chi ； Xiaochen Lai ； Shuwei Zhang ； He Guo ； Zhilei Ren

《電腦學刊》 31卷4期 (2020/08) Pp. 28-41

https://doi.org/10.3966/199115992020083104003

摘要

Hyper-heuristics aim to automate the adaptation of heuristics to solve hard computational search problems, which solves problems from different domains by manipulating the domain-specific Low Level Heuristics (LLHs). However, despite the promising results obtained by various hyper-heuristics, when faced with new problem domains, the design and implementation of the LLHs require significant expense. Moreover, the intrinsic complexity of large scale problem instances also poses great challenge for hyper-heuristics, which makes the solving process time-consuming. In this paper, we propose a novel Decomposition and Mathematical Programming based Hyper-heuristic (DEMPH), which features the combination of the decomposition based problem solving and the generalization ability of mathematical programming solvers. We develop strategies to decompose the large scale problem instances to sub-problems, and apply the mathematical programming solver to solve the sub-problems. An adaptive high level strategy is employed to schedule the sub-problem selection strategies. Experiments on the generalized assignment problem and the three-index assignment problem indicate that DEMPH is able to tackle large scale problems efficiently, and generalize well on different type of instances.

關鍵字

AP3 ； decomposition ； GAP ； hyper-heuristic ； mathematical programming