Orthogonal Packing Feasibility, Two-Dimensional Knapsack Problems

Guntram Scheithauer
Additional contact information
Guntram Scheithauer: TU Dresden

Chapter Chapter 5 in Introduction to Cutting and Packing Optimization, 2018, pp 123-156 from Springer

Abstract: Abstract The Orthogonal Packing Feasibility Problem and the Orthogonal Knapsack Problem are basic problems in two- and higher-dimensional cutting and packing. For given dimensionality d ≥ 2, we consider a set of d-dimensional rectangular items (pieces) that need to be packed into the given container. The input data describe the container sizes, the item sizes, and, in case of a knapsack problem, the profit (value) coefficient of any item. Feasibility problem Knapsack problem two-dimensional Cutting problem two-dimensional Orthogonal packing problem The d-dimensional Orthogonal Packing Problem (dOPP) is the feasibility problem: decide whether all the m pieces can orthogonally be packed into the container without rotations. The d-dimensional Orthogonal Knapsack Problem (dOKP) asks for a subset of items of maximal total profit which can orthogonally be packed into the container without rotations. In the following, we describe a basic nonlinear and some integer linear programming models (for simplicity, frequently for d = 2). Afterwards we discuss some necessary conditions for the feasibility of an OPP instance. We continue with a short description of the graph-theoretical approach of Fekete and Sche pers (2004). Moreover, we also present some results concerning statements on the packability of a set of rectangular items into a container. Finally, we propose a (general) branch-and-bound algorithm based on the contour concept which allows to regard various additional restrictions and to construct fast heuristics.

Date: 2018
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-319-64403-5_5

Ordering information: This item can be ordered from
http://www.springer.com/9783319644035

DOI: 10.1007/978-3-319-64403-5_5

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().