Tackling Large-Scale and Combinatorial Bi-level Problems with a Genetic Programming Hyper-heuristic

in IEEE Transactions on Evolutionary Computation (2019)

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is a NP-hard problem. In this work, we tackle large-scale and combinatorial bi-level problems using GP ... [more ▼]

Combinatorial bi-level optimization remains a challenging topic, especially when the lower-level is a NP-hard problem. In this work, we tackle large-scale and combinatorial bi-level problems using GP Hyper-heuristics, i.e., an approach that permits to train heuristics like a machine learning model. Our contribution aims at targeting the intensive and complex lower-level optimizations that occur when solving a large-scale and combinatorial bi-level problem. For this purpose, we consider hyper-heuristics through heuristic generation. Using a GP hyper-heuristic approach, we train greedy heuristics in order to make them more reliable when encountering unseen lower-level instances that could be generated during bi-level optimization. To validate our approach referred to as GA+AGH, we tackle instances from the Bi-level Cloud Pricing Optimization Problem (BCPOP) that model the trading interactions between a cloud service provider and cloud service customers. Numerical results demonstrate the abilities of the trained heuristics to cope with the inherent nested structure that makes bi-level optimization problems so hard. Furthermore, it has been shown that training heuristics for lower-level optimization permits to outperform human-based heuristics and metaheuristics which constitute an excellent outcome for bi-level optimization. [less ▲]