.png){kind=icon}
.png){kind=icon}
Return
An exact algorithm for the multiple-choice Knapsack problem with setups
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cie.2023.109818.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In this paper, an exact method based on Benders' decomposition is proposed to solve the multiple-choice knapsack problem with setups. The designed method incorporates various techniques to bound the optimal solution effectively. The approach starts by constructing a feasible solution through a series of linear programming relaxations. Each relaxation is augmented with valid constraints to tightly bound both global and local optimal solutions. Subsequently, an initial interval search is established by computing its related lower and upper bounds. These bounds are obtained by solving two tailored linear programming relaxations that account for the cardinality constraint associated with variables representing the families. Once the search interval is determined, it is systematically scanned to find the optimal solution, if one exists. Benders' decomposition is used for each current sub-interval to bound the local optimal solution. Finally, the proposed method is empirically evaluated on benchmark instances extracted from the literature, where its achieved results are then compared with those obtained by the state-of-the-art Cplex solver. A substantial number of instances have been successfully solved through the proposed method, considering the persistent unresolved state of these instances up to now.
Keywords:
Integer programming
Benders
Knapsack
Optimality
Optimization
Journal
IF:
6.5
Papers:
1.0W
Citations:
3.8W