Bin Packing with Irregular Shapes

• Applicant: Professor Dr. Stefan Irnich
• Subject Area: Operations Management and Computer Science for Business Administration
• Term: since 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 561644927

Cutting and packing problems are two well-known combinatorial optimization problems. In cutting problems, a set of stock sheets has to be cut into smaller items so that a given demand is satisfied. In packing problems, a given set of items has to be packed into a minimum number of containers, also known as bins. The two types of problems are closely related and have many practical applications such as garment, shoe, and furniture manufacturing, automotive, shipbuilding, and metal processing industries, or in transportation and logistics. With the rising cost of raw materials, companies are putting greater emphasis on resource conversation and reducing material waste. Not only do companies benefit from improved planning, but so does the environment. A classic representative of cutting and packing problems is the one-dimensional bin packing problem (BPP). Given a set of items with different weights/sizes and a set of identical bins with a given capacity/length, the task is to pack all items into a minimum number of bins such that the capacity of each bin is respected. Although most of the scientific work deals with the one-dimensional case, a one-dimensional representation of an item and a bin is not sufficient in many practical applications. For example, in clothing and furniture manufacturing, length and width are relevant (two dimensions). In container and pallet loading, items and bins are three-dimensional objects. The shape of items and bins, whether they are regular or irregular, is another feature that characterizes a problem. In the two-dimensional case, an item is called regular if it can be completely described by at most two parameters, e.g., a rectangle that can be described by its length and width. In contrast, an item is said to be irregular if more than two parameters are needed to describe its shape accurately, e.g., a general polygon is considered irregular because it cannot be completely described by its width and length. We address the two-dimensional bin packing problem with irregular item shapes and bins and call this problem the irregular shape bin packing problem (ISBPP). The goal of the ISBPP is to place all items in a given set of bins in a non-overlapping manner, such that each item fits completely into one bin and the number of potentially different bins used is minimized. The placement aspect is typically modeled by a set of rules that describe how each type of item can be placed, e.g., describing whether and to what angle items can be rotated. We propose to solve ISBPPs using integer programming based optimization methods, namely a branch-price-and-cut algorithm in which subproblems are solved with a combinatorial Benders algorithm. This type of approach is novel and generic, as it offers the possibility of using different item and bin representations and associated application-tailored placement algorithms.

• DFG Programme: Research Grants