Experts at modelling constraint satisfaction problems CSPs carefully choose model reformulations 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 reformulations. A problem may be viewed and reformulated at various levels of abstraction. Equivalent reformulations may be simple at one such level, yet very difficult at another. Therefore we argue that it is essential for a system for the automatic reformulation of CSPs to reason at multiple levels of abstraction. Reformulations can then be made at the level of abstraction at which they are most straightforward. We describe how the CGRASS system, which currently reformulates individual CSP instances, could be augmented to reformulate models at various levels of abstraction and to refine models from one level to a less abstract level. The SONET problem, a realistic combinatorial optimisation problem, is used to illustrate our approach.
Back to "Barbara Smith - Publications on Constraint Programming"