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

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

0.00 Avg rating0 Votes
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:
Keywords: recreation & tourism
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.