A Lagrangean based solution algorithm for the knapsack problem with setups. (1st April 2020)

• Record Type: Journal Article
• Authors: Amiri, Ali
• Is Part Of: Expert systems with applications. Volume 143(2020)
• Publication Date: 2020-04-01
• Subjects: Knapsack problem with setups -- Lagrangean relaxation; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2019.113077
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: This paper studies the knapsack problem with setups. This paper presents an algorithm based on a Lagrangean relaxation of the problem. We used very large data sets to test the algorithm. The algorithm can solve near optimally the problem in reasonable amount of time. Abstract: We consider the knapsack problem with setups which is a generalization of the classical knapsack problem where the items belong to families and an item can be placed in the knapsack only if its family is selected. The problem has received increasing attention by researchers because of its theoretical significance and practical applications related to resource allocation. This paper presents an algorithm based on a Lagrangean relaxation of the problem that produces solutions whose quality can be assessed automatically with the algorithm itself without ever knowing the optimal solutions. We report results of an extensive computational study which show that the method can solve near optimally very large instances of the problem with up to 500 families and 2, 000, 000 items in reasonable amount of time. This study shows the merit of using the Lagrangean relaxation method to solve the current problem when the constraints to relax are chosen properly.