Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, August 18, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Mutsunori Yagiura (Kyoto University)
We examine various strategies for exact approaches to the 2-dimensional strip packing problem (2SP) with and without rotations. We first develop branch-and-bound algorithms based on sequence-pair representation. We then consider the perfect packing problem (PP), which is a special case of 2SP in that it calls for a packing of given rectangles without wasted space, and propose new branching rules and bounding operations in branch-and-bound algorithms for PP. Computational results on benchmark instances with up to 30 rectangles discloses that one of these rules is very effective especially for feasible instances of PP.
Automatic MiSe System Software Version 1.4803M | admin login