.png){kind=icon}
.png){kind=icon}
Return
Iterative integer linear programming-based heuristic for solving the multiple-choice knapsack problem with setups
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2023.122835.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper studies the multiple-choice knapsack problem with setup (MCKS) which is a generalization of the knapsack problem with setup (KPS) where the items can be processed in multiple periods. The Integer Linear Programming (ILP) of the MCKS shows its limitations when solved using CPLEX 12.7 solver, and the existing algorithms VNS&IP and VND-LB from the literature outperform the ILP and provide the best-known solutions but solve to optimality only 29 out of 120 instances, respectively. This paper is dedicated to exposing an Iterative Integer linear programming-based heuristic (IILP-H) that deals with the MCKS. The IILP-H has been experimented on the MCKS benchmark instances. A sensitivity analysis of the MCKS parameters is provided. A comparison of the IILP-H with the upper bound obtained by the CPLEX 12.7 solver and the best state-of-the-art algorithms has been conducted. The numerical results show that the IILP-H outperforms all the existing solving techniques when it comes to solution quality and computation time. It reaches 120 out of 120 best solutions, including 77 out of 120 optimal and 69 new best solutions. The complexity of the MCKS and the nature of the solutions obtained by the IILP-H are studied regarding the number of periods to which a family is assigned.
Keywords:
Knapsack Problem with setup
Multiple-Choice Knapsack Problem with Setups
Integer linear programming
Iterative Integer linear programming
Heuristic approach
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W
View more organizations