A Two-Stage epsilon-Constraint Strategy-Based Heuristic for Bi-Objective Quadratic Multiple Knapsack Problems
Résumé
In this paper, we propose a two-stage method for solving the Bi-Objective Quadratic Multiple Knapsack Problem (BO-QMKP). The method combines both a special local branching (the first stage) and the epsilon-constraint (the second stage) strategies, where the local branching tries to intensify the search process while a series of epsilon-constraints are added to tailor a diversification of the search space. The method is based on solving a series of mono-objective optimization problems: from the current problem, provided by combining the original problem and an epsilon-constraint (using a single objective function). an optimization phase is applied in order to generate a set of non-dominated solutions. A preliminary experimental part is given, where the performance of the proposed two-stage method is evaluated on a set of benchmark containing large-scale instances. Its provided results are compared to those achieved by one of the best method available in the literature. Encouraging results have been obtained.