| 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. |