Bounds for nested knapsack problems

Robert E. Johnston, Lutfar R. Khan

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

Abstract

In this paper, a specific nested knapsack problem is considered and expressed as an integer linear programme. Nested knapsack problems can occur as subproblems of an important type of the cutting stock problem where there are successive cutting stages. In these problems only splitting (and not regrouping) of knapsack items is allowed between each stage. A series of a priori bounds, which are also applicable to bin packing problems, are established to assist in solving this problem.

Original languageEnglish
Pages (from-to)154-165
Number of pages12
JournalEuropean Journal of Operational Research
Volume81
Issue number1
DOIs
Publication statusPublished - 16 Feb 1995

Keywords

  • Cutting stock
  • Knapsack
  • Nesting
  • Packing

Cite this