Cutting and Packing Problems

• Frederico Dusberger
• Günther Raidl

Cutting and packing problems occur in a multitude of industrial or other real-world applications such as

• glass, paper and steel cutting,
• container or pallet loading,
• VLSI design,
• and many other applications.

Usually items have to be cut from raw material and waste should be minimized, or the number of bins/containers needed to pack given items has to be minimized. In our research we dealt (until now) with two-dimensional bin packing problems where only guillotineable cutting/packing patterns are allowed.

Another kind of packing problems are the so called Knapsack Problems. Where items with an associated profit have to be packed into one or more knapsacks, and the profit has to be maximized. There are several variants of knapsack problems, such as the classical knapsack problem, multiconstrained knapsack problems, multiple knapsack problems, and many others. In our research we mainly deal with multiconstrained knapsack problems.

Solving cutting and packing problems can be done in various ways, we developed metaheuristics and exact algorithms for dealing with those problems. Especially the combination of evolutionary algorithms with problem specific heuristics, local and global optimization techniques are considered. Please see also our page on metaheuristics and evolutionary computation and the page on hybrid optimization techniques.