Iterated Local Search for the Disjunctively Constrained Knapsack Problem: Reproducible Implementation and Computational Study on the DCKP-Set I

This paper presents a preliminary study with a heuristic solver for the Disjunctively Constrained Knapsack Problem (DCKP) based on Iterated Local Search (ILS). The method combines a profit-based greedy construction, a Variable Neighborhood Descent (VND) with insertion and swap neighborhoods, and a destroy-and-repair perturbation, implemented in C++ with a focus on efficiency and reproducibility. The experiments cover 100 instances of the DCKP-Set~I benchmark, with five runs per instance and a 1000-second time limit each — totaling 500 runs, all with feasible solutions. Compared to the best-known values reported by Wei et al. [2023], the algorithm reaches an average gap of 2.72%, remaining close to the reference in Group 2 and in the sparse classes of Group 1. Performance is lower in the small, dense classes of Group 1 — a pattern associated with the combination of small instances and high conflict density, rather than density alone.