An Exact Algorithm for General Orthogonal n-dimensional Knapsack Problems

Schepers, Jörg (1997) An Exact Algorithm for General Orthogonal n-dimensional Knapsack Problems.
Published In: Selected papers of the Symposium on Operations Research (SOR) : Braunschweig, September 3 - 6, 1996 Springer 1997, pp. 129-133.

Abstract

The n-dimensional orthogonal knapsack problem has a wide range of practical applications, including packing, cutting and scheduling. We present a new approach for its exact solution using a two-level tree search algorithm. A key role plays a graph-theoretical characterization of packing patterns that allows us to deal with classes of packing pattern that are symmetrical in a certain sense, instead of single ones. Computational results are reported for two-dimensional test problems from literature.


Actions:
Download: [img] Postscript - Preprinted Version
Download (164kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-258
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:46
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/258