CGRASS: A system for transforming constraint satisfaction problems

A M Frisch; I Miguel; T Walsh

CGRASS: A system for transforming constraint satisfaction problems

A M Frisch, I Miguel, T Walsh

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 language	English
Title of host publication	RECENT ADVANCES IN CONSTRAINTS
Editors	B OSullivan
Place of Publication	BERLIN
Publisher	Springer
Pages	15-30
Number of pages	16
ISBN (Print)	3-540-00986-8
Publication status	Published - 2003
Event	Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming - CORK Duration: 19 Jun 2002 → 21 Jun 2002

Conference

Conference	Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming
City	CORK
Period	19/06/02 → 21/06/02

Cite this

@inproceedings{61af6d7faa9c45ff97683c6a2872a0bb,

title = "CGRASS: A system for transforming constraint satisfaction problems",

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.",

author = "Frisch, {A M} and I Miguel and T Walsh",

year = "2003",

language = "English",

isbn = "3-540-00986-8",

pages = "15--30",

editor = "B OSullivan",

booktitle = "RECENT ADVANCES IN CONSTRAINTS",

publisher = "Springer",

address = "Germany",

note = "Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming ; Conference date: 19-06-2002 Through 21-06-2002",

}

TY - GEN

T1 - CGRASS: A system for transforming constraint satisfaction problems

AU - Frisch, A M

AU - Miguel, I

AU - Walsh, T

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 3-540-00986-8

SP - 15

EP - 30

BT - RECENT ADVANCES IN CONSTRAINTS

A2 - OSullivan, B

PB - Springer

CY - BERLIN

T2 - Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming

Y2 - 19 June 2002 through 21 June 2002

ER -