article · Journal of Korean Institute of Industrial Engineers · 2014

The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem

Cited by 0Open access

Abstract

The multi-divisional knapsack problem is defined as a binary knapsack problem where each mutually exclusive division has its own capacity. In this paper, we present an extension of the multi-divisional knapsack problem that has generalized multiple-choice constraints. We explore the linear programming relaxation (P) of this extended problem and identify some properties of problem (P). Then, we develop a transformation which converts the problem (P) into an LP knapsack problem and derive the optimal solutions of problem (P) from those of the converted LP knapsack problem. The solution procedures have a worst case computational complexity of order <TEX>$O(n^2{\log}\;n)$</TEX>, where n is the total number of variables. We illustrate a numerical example and discuss some variations of problem (P).

Cite this paper

APA 7

Won, J.-Y. (2014). The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem. Journal of Korean Institute of Industrial Engineers, 40(4), 396–403. https://doi.org/10.7232/jkiie.2014.40.4.396

MLA 9

Won, Joong-Yeon. “The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem.” Journal of Korean Institute of Industrial Engineers, vol. 40, no. 4, 2014, pp. 396–403, https://doi.org/10.7232/jkiie.2014.40.4.396.

Chicago

Won, Joong-Yeon. 2014. “The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem.” Journal of Korean Institute of Industrial Engineers 40 (4): 396–403. https://doi.org/10.7232/jkiie.2014.40.4.396.

Harvard

Won, J.-Y. (2014) ‘The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem’, Journal of Korean Institute of Industrial Engineers, 40(4), pp. 396–403. Available at: https://doi.org/10.7232/jkiie.2014.40.4.396.

BibTeX

@article{won2014generalized,
  title = {{The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem}},
  author = {Won, Joong-Yeon},
  journal = {Journal of Korean Institute of Industrial Engineers},
  volume = {40},
  number = {4},
  pages = {396--403},
  year = {2014},
  doi = {10.7232/jkiie.2014.40.4.396}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

The Generalized Multiple-Choice Multi-Divisional Linear Programming Knapsack Problem

Abstract

Cite this paper

Comparison and Analysis of Algorithms for the 0/1 Knapsack Problem

The Partial Choice Recoverable Knapsack Problem

Analysis of 0/1 Knapsack Problem Using Deterministic and Probabilistic Techniques