Gecode: Publications

Modeling Irregular Shape Placement Problems with Regular Constraints

Mikael Z. Lagerkvist, Gilles Pesant.

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.

In: First Workshop on Bin Packing and Placement Constraints BPPC'08. 2008.