The knapsack problem with setup (KPS) is a challenging problem in combinatorial optimization. This paper deals with the generalized problem of KPS called multiple-choice knapsack problem with setup (MCKS). The MCKS has several applications in industry such as the assignment of production to plants. A combination of Iterated local search with integer linear programming is provided and enhanced by LP-relaxation to solve the MCKS. The provided matheuristic is called LP-ILS&IP. A sensitivity analysis is provided the justify the components of the LP-ILS&IP and numerical experiments are conducted on a set of 120 benchmark instances to show the competitiveness of the LP-ILS&IP compared to the best state-of-the-art solving techniques.
Efficient mat heuristic for solving the Multiple-Choice Knapsack Problem with Setup
33 Views
6 Downloads