Cutting and Packing Problems

Problems of cutting and packing objects have been extensively studied for many years because of the numerous real-world applications—for instance, in the clothing, logistics, manufacturing, and material industries. They can be classified in three ways according to their dimensions: The one-dimensional problem is the most basic category of problems including knapsack problems, bin packing problems, and cutting stock problems. The two-dimensional geometric problems include rectangle packing problems, circle packing problems, and polygon packing problems. The three-dimensional problem is the most difficult category and has applications in container loading, cargo and warehouse management and so forth. Most of these variants are NP-hard, since they contain as a special case the knapsack problem or the bin packing problem, which are already known to be NP-hard. Therefore, heuristics and metaheuristics are essential for designing practical algorithms for these problems. In addition to practical algorithms for solving a wide variety of cutting and packing problems, the book also considers another feature of cutting and packing problems: the need to develop powerful geometric tools to handle the wide variety and complexity of shapes that need to be packed.