Linear Programming-based algorithms for orthogonal packing

• Applicant: Privatdozent Dr. Gleb Belov
• Subject Area: Mathematics
• Term: from 2009 to 2013
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 144098350

The goal is to develop efficient exact and heuristic methods for orthogonal packing in two and more dimensions using Linear Programming (LP). The basic Orthogonal Packing Problem (OPP) is a decision problem asking if a set of orthogonal items can be placed in a given orthogonal container with all sides parallel, without rotation. This problem relates to the orthogonal strip-packing, bin-packing, and knapsack problems as well as to scheduling problems. Today’s well-known methods mostly possess purely combinatorial structure (search strategies and bounds). However, it has been known for several years that the one-dimensional relaxation of OPP provides strong bounds which are computable by Linear Programming. Our working group has integrated such bounds in the interval graph algorithm (a previously known exact method), which lead to its improvement. This suggests further research in this direction. The simplest effort would be just to integrate the new bounds in existing approaches without changing the search strategy. However, an interesting question is the adaptation of the search strategy. This seems to be a rather involved task because of the combinatorial properties of the problem (e.g., non-overlapping conditions, non-interruptedness of the location in each dimension).

• DFG Programme: Research Grants
• International Connection: Russia
• Participating Persons: Dr. Vadim Kartak; Dr. Guntram Scheithauer