CGRASS: A System for Transforming Constraint Satisfaction Problems

Alan M. Frisch; Ian Miguel; Toby Walsh

doi:10.1007/3-540-36607-5_2

CGRASS: A System for Transforming Constraint Satisfaction Problems

Alan M. Frisch, Ian Miguel, Toby Walsh

Computer Science

Research output: Contribution to conference › Paper › peer-review

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	Undefined/Unknown
Pages	15-30
DOIs	https://doi.org/10.1007/3-540-36607-5_2
Publication status	Published - 2002

Access to Document

10.1007/3-540-36607-5_2

http://link.springer.de/link/service/series/0558/bibs/2627/26270015.htm

Cite this

@conference{d756ec8c32864838b27e6d9416edd207,

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, {Alan M.} and Ian Miguel and Toby Walsh",

year = "2002",

doi = "10.1007/3-540-36607-5_2",

language = "Undefined/Unknown",

pages = "15--30",

}

TY - CONF

T1 - CGRASS

T2 - A System for Transforming Constraint Satisfaction Problems

AU - Frisch, Alan M.

AU - Miguel, Ian

AU - Walsh, Toby

PY - 2002

Y1 - 2002

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.

U2 - 10.1007/3-540-36607-5_2

DO - 10.1007/3-540-36607-5_2

M3 - Paper

SP - 15

EP - 30

ER -