University of York, Department of Computer Science

Implied Constraints Project: Frequently Asked Questions


[Home | People | Publications | Presentations | Links | Contact]
What is an implied constraint?

A logical consequence of the initial specification of the problem.

Why are implied constraints useful?

Though adding an implied constraint to the specification of a constraint satisfaction problem does not change the set of solutions, it can reduce the amount of search the solver has to do.

What is the difference between an implied constraint and a redundant constraint?

Redundant constraints are implied by the initial problem specification, but give no extra propagation. They therefore just add overhead.

Why is it hard to generate implied constraints?

The generation of some of the best implied constraints involves complex reasoning steps which are difficult to automate or even to formulate in a systematic way. Some implied constraints are also more useful than others, so it is important to be able to prune redundant constraints. However, quantifying an answer to the problem can be found without search. Typically, this process will be slower than searching from the initial problem, however, so at some point we should stop inferring new constraints and start to search. The (difficult) question is when to do this.

Is a symmetry-breaking constraint an implied constraint?

No - symmetry-breaking constraints are not logical consequences of the initial specification and breaking symmetry reduces the set of solutions. However, breaking symmetry is often an important first step which helps to generate implied constraints. Therefore, the automated generation of symmetry-breaking constraints is one of the key issues that we are addressing.

How can implied constraints be generated automatically?

We are looking at two complementary methods. The first adapts Proof Planning to classical planning operators) that encapsulate what we know of generating implied constraints by hand to generate useful implied constraints. The second is an inductive approach using the HR mathematical discovery program to spot patterns in solutions to small instances of a class of problems which are then used to generate implied constraints for use in solving larger instances from the same class.

This web-page is maintained by J. Pickering, and was last changed on Sun 14 Oct 2001.