Orthogonal Packing Feasibility, Two-Dimensional Knapsack Problems

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.