Program of BPPC'08

1.30-2.30 Invited talk by François Clautiaux. Exact methods for rectangle placement problems
Abstract:  Rectangle placement problems are among the main issues in many two-dimensional cutting and packing problems. They consist in determining if a set of small rectangular pieces can be packed in a large rectangle without overlapping. The talk will focus on exact methods for two well-known rectangle placement problems: the unconstrained problem, and the problem with "guillotine cuts" only. Some feasibility tests, graph-theoretical models, branch-and-bound and constraint-programming techniques will be surveyed for both problems.
2.30-3.00 Helmut Simonis and Barry O'Sullivan. Using Global Constraints for Rectangle Packing
Abstract: In this paper we solve the optimal rectangle packing problem using cumulative and disjoint constraints in Sicstus Prolog with a novel decomposition method, together with a specialized search routine and various model enhancements. We improve the best known runtimes by up to a factor of 300.
3.00-3.30 Mikael Z. Lagerkvist and Gilles Pesant. Modeling Irregular Shape Placement Problems with Regular Constraints
Abstract: The regular constraint (Pesant, CP04) is a powerful global constraint with many possible uses. It was introduced to model certain common constraints in rostering problems.  In this paper we show how to use it to model placement problems with irregular shapes.  The technique is illustrated by solving Pentominoes and Solitaire Battleships. The efficiency of the basic model is improved by projecting out irrelevant information.  Experimental results on Pentomino packing benchmark instances indicate that this simple approach can be competitive with specialized algorithms.  From the applications we can identify some areas for improvement in the implementation of regular constraints.
3.30-4.00 Coffee Break
4.00-4.30 Arnaud Malapert, Christelle Gueret, Narendra Jussien, Andre Langevin and Louis-Martin Rousseau. Two-dimensional Pickup and Delivery Routing Problem with Loading Constraints
Abstract: In this paper, a special case of the vehicle routing problem in which the demands consist in a set of rectangular two-dimensional weighted items is considered. The vehicles have a two-dimensional loading surface and a maximum weight capacity. These problems have a routing and a packing component. A framework to handle the loading of a vehicle is proposed. A Constraint Programming loading model based on a scheduling approach is developed. It is also shown that the non-overlapping rectangle constraint can be extended to handle a practical constraint called sequential loading constraint.
4.30-5.00 Bertrand Neveu and Gilles Trombettoni. An Efficient Method for Strip Packing Based on Local Search and a Randomized Best-Fit
Abstract: We present a metaheuristic with no user-defined parameter for handling the strip-packing problem, a variant of the famous 2D bin-packing. The performance of our approach is due to several devices.  We propose a move, based on the geometry of the layout, which is made incremental by maintaining the set of maximal holes. For escaping from local minima, the Intensification Diversification Walk (ID Walk) metaheuristic is used. ID Walk manages only one parameter that is automatically tuned by our tool.

We focus here on the greedy heuristics used to perform the moves and to compute the first layout before running the metaheuristic. In particular, we propose a variant of the well-known Best-fit (decreasing) (BF), called RBF, in which the criterion (i.e., height, width, perimeter, surface) changes every time a hole is selected. This simple way to randomize the most efficient greedy strategy is a key for obtaining good bounds while diversifying the layouts.

This paper provides an experimental evidence that a local search approach can be competitive with the best known incomplete algorithms.
5.00-5.30 Waldemar Kocjan and Kenneth Holmström. Generating Stable Loading Patterns for Pallet Loading Problems 
Abstract: This paper describes an integer programming model for generating stable loading patterns for the Pallet Loading Problem. The algorithm always gives optimal or near-optimal utilization of the pallet area and fulfills stability criteria for 98% of the test cases.
5.30-6.00 Alex Fukunaga. Repairing Bin Packing Constraints
Abstract: We consider a variant of the bin packing problem, where items are initially assigned to bins, and the goal is to rearrange the items in the minimum number of steps such that the capacity constraints are satisfied. We consider two search spaces for solving this problem, a commitment-based search space and a difference-based search space. We evaluate depth-first branch and bound and IDA* algorithms in these search spaces, and showthat IDA* in the commitment-based search space significantly outperforms the alternatives.