A threshold search based memetic algorithm for the disjunctively constrained knapsack problem

Zequn Wei

doi:10.1016/j.cor.2021.105447

Return

A threshold search based memetic algorithm for the disjunctively constrained knapsack problem

2021-12-01

Zequn Wei

Jin‐Kao Hao *

DOI：10.1016/j.cor.2021.105447

Original

Save

View PDF

Abstract

En 中文

The disjunctively constrained knapsack problem consists in packing a subset of pairwisely compatible items in a capacity-constrained knapsack such that the total profit of the selected items is maximized while satisfying the knapsack capacity. DCKP has numerous applications and is however computationally challenging (NP-hard). In this work, we present a threshold search based memetic algorithm for solving the DCKP that combines the memetic framework with threshold search to find high quality solutions. Extensive computational assessments on two sets of 6340 benchmark instances in the literature demonstrate that the proposed algorithm is highly competitive compared to the state-of-the-art methods. In particular, we report 24 and 354 improved best-known results (new lower bounds) for Set I (100 instances) and for Set II (6240 instances), respectively. We additionally apply the approach to solve a real-life daily photograph scheduling problem of an earth observation satellite. We analyze the key algorithmic components and shed lights on their roles for the performance of the algorithm.

Keywords:

Knapsack problems

Disjunctive constraint

Threshold search

Heuristics

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.