An evolutionary path relinking approach for the quadratic multiple knapsack problem

摘要

The quadratic multiple knapsack problem (QMKP) is a challenging combinatorial optimization problem with numerous applications. In this paper, we propose the first evolutionary path relinking approach (EPR) for solving the QMKP approximately. This approach combines advanced features both from the path relinking (PR) method and the responsive threshold search algorithm. Thanks to the tunneling property which allows a controlled exploration of infeasible regions, the proposed EPR algorithm is able to identify very high quality solutions. Experimental studies on the set of 60 well-known benchmarks and a new set of 30 large-sized instances show that EPR outperforms several state-of-the-art algorithms. In particular, for the 60 conventional benchmarks, it discovers 10 improved results (new lower bounds) and matches the best known result for the remaining 50 cases. More significantly, EPR demonstrates remarkable efficacy on the 30 new larger instances by easily dominating the current best performing algorithms across the whole instance set. Key components of the algorithm are analyzed to shed lights on their impact on the proposed approach.