Publications by Gilles Pesant

Publications by Gilles Pesant

Modeling Irregular Shape Placement Problems with Regular Constraints

2008

Authors: Mikael Z. Lagerkvist, Gilles Pesant

Venue: First Workshop on Bin Packing and Placement Constraints (BPPC'08)

The regular constraint 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.

PDF