Pentomino exclusion and spanning. IP-formulation, valid inequalities and facets

Abstract

Pentomino exclusion asks to delete a minimum numberof 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.