Responsive strategic oscillation for solving the disjunctively constrained knapsack problem

Zequn Wei, Jin-Kao Hao, Jintong Ren and Fred Glover

European Journal of Operational Research, 2023, vol. 309, issue 3, 993-1009

Abstract: 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 feasible local search to find high-quality local optimal solutions and employs a strategic oscillation search with a responsive 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 algorithm is able to discover 39 new lower bounds and match all the remaining best-known results. Additional experiments are performed on 21 real-world instances of a daily photograph scheduling problem. The critical components of the algorithm are experimentally assessed.

Keywords: Combinatorial optimization; Disjunctively constrained knapsack problem; Heuristics; Strategic oscillation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723001248
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:309:y:2023:i:3:p:993-1009

DOI: 10.1016/j.ejor.2023.02.009

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().