Article ID: | iaor20021416 |
Country: | Belgium |
Volume: | 40 |
Issue: | 1/2 |
Start Page Number: | 25 |
End Page Number: | 45 |
Publication Date: | Jan 2000 |
Journal: | Belgian Journal of Operations Research, Statistics and Computer Science |
Authors: | Plastria Frank |
Keywords: | recreation & tourism |
Pentomino exclusion asks to delete a minimum number of cells from a square grid forbidding placement of any pentomino shape within the remaining cells, while pentomino spanning asks for finding a minimum number of different disjoint pentominoes disallowing placement of any additional pentomino. We discuss here IP formulations for each of these two problems of recreational mathematics. Several families of symmetry breaking constraints and valid inequalities are derived, many of which are shown to be facet generating.