Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits

• DOI: 10.1111/itor.13512
• Publication Date: 2024-07-26T09:45:02Z
• Authors: Qing Zhou; Jin‐Kao Hao; Zhong‐Zhong Jiang; Qinghua Wu
• Keywords: 0202 electrical engineering, electronic engineering, information engineering; 02 engineering and technology

Abstract The knapsack problem (KP) with forfeits is a generalized KP that aims to select some items, among set of candidate maximize profit function without exceeding the capacity. Moreover, forfeit cost incurred and deducted from when both incompatible items are placed in knapsack. This relevant model for number applications however computationally challenging. We present hybrid heuristic method tackling this combines evolutionary search adaptive feasible infeasible find high‐quality solutions. A streamlining technique designed accelerate evaluation solutions, which increases significantly computational efficiency algorithm. assess algorithm on 120 test instances demonstrate its dominance over best performing approaches literature. Particularly, we show 94 improved lower bounds. investigate essential algorithmic components understand their roles.