Responsive strategic oscillation for solving the disjunctively constrained knapsack problem

This paper presents a responsive strategic oscillation algorithm for the NP-hard disjunctively constrained knapsack problem, which has a variety of applications. The algorithm uses an effective f easible local search to find high-quality local optimal solutions and employs a strategic oscillation search with a re-sponsive filtering strategy to seek still better solutions by searching along the boundary of feasible and infeasible regions. The algorithm additionally relies on a frequency-based perturbation to escape deep local optimal traps. Extensive evaluations on two sets of 6340 benchmark instances show that the algo-rithm is able to discover 39 new lower bounds and match all the remaining best-known results. Addi-tional experiments are performed on 21 real-world instances of a daily photograph scheduling problem. The critical components of the algorithm are experimentally assessed.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

This paper presents a responsive strategic oscillation algorithm for the NP-hard disjunctively constrained knapsack problem, which achieves high-quality solutions by employing feasible local search and strategic oscillation search. The algorithm also uses a frequency-based perturbation to escape from local optimal traps. Extensive evaluations on benchmark instances and real-world instances demonstrate the effectiveness of the algorithm.