CGRASS: A system for transforming constraint satisfaction problems

Alan M. Frisch, Ian Miguel, Toby Walsh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

19 Citations (Scopus)

Abstract

Experts at modelling constraint satisfaction problems (CSPs) carefully choose model transformations to reduce greatly the amount of effort that is required to solve a problem by systematic search. It is a considerable challenge to automate such transformations and to identify which transformations are useful. Transformations include adding constraints that are implied by other constraints, adding constraints that eliminate symmetrical solutions, removing redundant constraints and replacing constraints with their logical equivalents. This paper describes the Cgrass (Constraint Generation And Symmetry-breaking) system that can improve a problem model by automatically performing transformations of these kinds. We focus here on transforming individual CSP instances. Experiments on the Golomb ruler problem suggest that producing good problem formulations solely by transforming problem instances is, generally, infeasible. We argue that, in certain cases, it is better to transform the problem class than individual instances and, furthermore, it can sometimes be better to transform formulations of a problem that are more abstract than a CSP.

Original languageEnglish
Title of host publicationRecent Advances in Constraints - Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, Selected Papers
EditorsBarry O'Sullivan
PublisherSpringer-Verlag
Pages15-30
Number of pages16
ISBN (Print)9783540366072
DOIs
Publication statusPublished - 2003
EventJoint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2002 - Cork, Ireland
Duration: 19 Jun 200221 Jun 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2627
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceJoint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2002
Country/TerritoryIreland
CityCork
Period19/06/0221/06/02

Fingerprint

Dive into the research topics of 'CGRASS: A system for transforming constraint satisfaction problems'. Together they form a unique fingerprint.

Cite this