.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Knapsack Problem with setup
Multiple-Choice Knapsack Problem with Setups
Integer linear programming
Iterative Integer linear programming
Heuristic approach
期刊
IF:
7.5
论文数:
2.9W
被引数:
10.2W
机构
引用论文
The dynamic space allocation problem: Applying hybrid GRASP and Tabu search metaheuristics动态空间分配问题: 应用混合抓取和禁忌搜索元启发式
OAAI
OAAI分享收藏Morphological and Immunohistochemical Examination of Lymphoproliferative Lesions Caused by Marek’s Disease Virus in Breeder Chickens.png)
AnimalsOAAI
AnimalsIF0
OAAI分享收藏
查看更多内容