A dynamic programming algorithm for the Knapsack Problem with Setup

被引：31
|
作者：
Chebil, Khalil [1 ]
Khemakhem, Mahdi [1 ]
机构：
[1] Univ Sfax, LOGIQ, Sfax, Tunisia
来源：
COMPUTERS & OPERATIONS RESEARCH | 2015年 / 64卷
关键词：
Knapsack problems; Setup; Dynamic programming; Combination; Production planning;
D O I：
10.1016/j.cor.2015.05.005
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
The Knapsack Problem with Setup (KPS) is a generalization of the classical Knapsack problem (KP), where items are divided into families. An individual item can be selected only if a setup is incurred for the family to which it belongs. This paper provides a dynamic programming (DP) algorithm for the KPS that produces optimal solutions in pseudo-polynomial time. In order to reduce the storage requirements of the algorithm, we adopt a new technique that consists in converting a KPS solution to an integer index. Computational experiments on randomly generated test problems show the efficiency of the DP algorithm compared to the ILOG's commercial product CPLEX 12.5. (C) 2015 Elsevier Ltd. All rights reserved.
引用
收藏
页码：40 / 50
页数：11
相关论文
共 50 条
  • [1] A dynamic programming algorithm for the bilevel knapsack problem
    Brotcorne, Luce
    Hanafi, Said
    Mansi, Raid
    OPERATIONS RESEARCH LETTERS, 2009, 37 (03) : 215 - 218
  • [2] LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
    Masmoudi, Malek
    Adouani, Yassine
    Jarboui, Bassem
    INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2024, 31 (03) : 1890 - 1916
  • [3] The Parallel Processing Approach to the Dynamic Programming Algorithm of Knapsack Problem
    Sin, Si Thu Thant
    PROCEEDINGS OF THE 2021 IEEE CONFERENCE OF RUSSIAN YOUNG RESEARCHERS IN ELECTRICAL AND ELECTRONIC ENGINEERING (ELCONRUS), 2021, : 2252 - 2256
  • [4] A lifted-space dynamic programming algorithm for the Quadratic Knapsack Problem
    Fomeni, Franklin Djeumou
    DISCRETE APPLIED MATHEMATICS, 2023, 335 : 52 - 68
  • [5] A Dynamic Programming Algorithm for Solving Bi-Objective Fuzzy Knapsack Problem
    Singh, V. P.
    Chakraborty, D.
    MATHEMATICS AND COMPUTING, 2015, 139 : 289 - 306
  • [6] A reduction dynamic programming algorithm for the bi-objective integer knapsack problem
    Rong, Aiying
    Figueira, Jose Rui
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2013, 231 (02) : 299 - 313
  • [7] Unbounded knapsack problem: Dynamic programming revisited
    Andonov, R
    Poirriez, V
    Rajopadhye, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 123 (02) : 394 - 407
  • [8] A Dynamic Programming Heuristic for the Quadratic Knapsack Problem
    Fomeni, Franklin Djeumou
    Letchford, Adam N.
    INFORMS JOURNAL ON COMPUTING, 2014, 26 (01) : 173 - 182
  • [9] Modeling and solving of knapsack problem with setup based on evolutionary algorithm
    He, Yichao
    Wang, Jinghong
    Liu, Xuejing
    Wang, Xizhao
    Ouyang, Haibin
    MATHEMATICS AND COMPUTERS IN SIMULATION, 2024, 219 : 378 - 403
  • [10] An effective dynamic programming algorithm for the minimum-cost maximal knapsack packing problem
    Furini, Fabio
    Ljubic, Ivana
    Sinnl, Markus
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2017, 262 (02) : 438 - 448
12345