Dagstuhl Seminar 07112 took place from Wednesday, 14th March, 2007 to Friday, 16th March. There were 17 participants from a total of 9 different countries. The seminar was led by Graham Kendall and Karen Daniels. Jan van der Veen was designated to collate the proceedings. The schedule of talks is listed below.

Seminar 07112’s talks fostered productive discussions on problems of common interest to cutting, packing and space allocation researchers, with most of the presentations concerned with cutting and packing but it is apparent that “Cutting and Packing” and “Space Allocation” are closely related areas.

Some of the work addressed two-dimensional packing, with other presentations concentrating on the three-dimensional variant. Three-dimensional research is a largely an unexplored research area, with scope for significant advances to be made. At this seminar we heard presentations which outlined a number of different approaches that are being utilised. For example:

• Packing boxes into containers using heuristics.
• Independent sets in conflict graphs were used for some box/container packing problems
• Convex and non-convex three-dimensional shapes were packed into minimal sized containers (with discrete rotations) using randomization for global search combined with gradient descent for local optimization.

The two-dimensional problem remains an active area of research, with heuristics and meta-heuristics being used for packing both rectangles and irregular shapes polygons. Despite its long history, there still remain many open problems and challenges in two-dimensional packing.

The space allocation talks dealt with two different topics. 1) The optimisation of commercial (retail) shelf space allocation. This was formulated as an integer programming problem which was optimised using simulated annealing combined with heuristic search. 2) Improving the utilisation of university teaching space. This talk outlined the many challenges that face university administrators and planners and emphasised the need for progress in this area to support them in tackling this important problem.

Seminar 07112 was held during the same week as Seminar 07111, whose theme was Computational Geometry (CG). CG is a subfield of Computer Science that concerns the design, implementation, and analysis of efficient geometric algorithms on a computer. Analysis includes proofs of correctness and estimates of the amount of execution time and storage space required by the algorithms. Geometric problems are at the core of the problems in cutting, packing, and space allocation, so it was helpful to exchange ideas between the two seminars.

In addition to impromptu discussions between the two groups, there were four planned sessions that involved some, or all, of both groups.

1. This was an invited presentation by Sandor Fekete (Orthogonal Packing Problems and Benchmark Instances). This talk outlined some of his research as well as introducing the seminar to a web site (packlib) which provides access to various benchmark datasets, as well as a bibliography.
2. This was also an invited presentation by a member of the computational geometry community. Dan Halperin’s talk (Arrangements and Their Applications: Recent Developments) included information on CGAL (the Computational Geometry Algorithm Library). This library, partly designed by Halperin, includes code to perform some basic geometric operations of importance to cutting and packing researchers.
3. As part of our seminar we held Open Problem Sessions, which was attended by several members from the computational geometry seminar. There was recognition of the need to understand the search landscape for cutting, packing and space layout problems. Rotational Minkowski sum operations are also needed because some packing problems allow arbitrary shape orientations. The Minkowski sum is the vector sum of two point sets and it is very useful in overlap questions that arise in cutting and packing. It was felt that the two communities could work more closely together in developing a set of library functions that the cutting and packing community could call upon (for example, no fit polygons etc.).
4. We also held a joint session (Thursday afternoon), where members of both seminars came together to hear presentations given by representatives from both seminars (see the schedule above).

As a result of all these interchanges, attendees of Seminar 071112 developed a better appreciation of the kinds of geometric problems that cutting and packing researchers need solutions for and Seminar 07112 members became more aware of the progress that has been made in recent years by CG researchers, particularly with respect to the Minkowski sum.

In summary, the seminar was felt to be a great success and there are many opportunities to hold related Dagstuhl seminars in the future.

Finally, we would like to thank the Dagstuhl organisers for providing excellent service and support both before, during and after the seminar. In particular, Annette Beyer was very helpful and sympathetic to our ever changing circumstances.