TY - GEN
T1 - CGRASS
T2 - Joint ERCIM/CologNet International Workshop on Constraint Solving and Constraint Logic Programming, 2002
AU - Frisch, Alan M.
AU - Miguel, Ian
AU - Walsh, Toby
N1 - Funding: This project is supported by EPSRC Grant GR/N16129. The third author is supported by Science Foundation Ireland.
PY - 2003/1/1
Y1 - 2003/1/1
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.
UR - https://doi.org/10.1007/3-540-36607-5
U2 - 10.1007/3-540-36607-5_2
DO - 10.1007/3-540-36607-5_2
M3 - Conference contribution
AN - SCOPUS:7044249168
SN - 9783540366072
T3 - Lecture notes in computer science
SP - 15
EP - 30
BT - Recent advances in constraints
A2 - O'Sullivan, Barry
PB - Springer-Verlag
CY - Heidelberg
Y2 - 19 June 2002 through 21 June 2002
ER -