Previous Up Next

3.3  General Guidelines for the Use of the IC library

Whilst IC has been designed to provide a flexible, consistent and yet powerful framework for many sorts of constraint satisfaction problems, it can not be all things to all people.

There are circumstances under which IC will not propagate all possible information, for reasons of efficiency.

It is the purpose of this section to point out ways that may help IC to solve problems more efficiently.

Typical constraint satisfaction problems are solved by iteratively propagating information from basic constraints until no more propagation can take place (i.e. a fixed point has been reached), and then reducing the domain of a variable so as to prompt more propagation.

As with most constraint solvers the propagation provided by the builtin constraints is rarely able to solve large problems completely without the need for some form of search. A number of factors affect the speed of the propagation phase.

  1. The size of the initial domains. Smaller domains typically result in propagation reaching a fixed point sooner. So give explicit initial domains to as many variables as possible.
  2. Integer domains allow more propagation. An important point to note here is that (as in mathematics) IC treats integers as a strict subset of the reals, and as such the integer domain 0 .. 100 contains significantly fewer values than the real domain 0.0 .. 100.0. With this in mind, IC attempts to infer integrality where possible (e.g. the sum of two integer variables is constrained to be integer), however integer domains (where applicable) should be used in user code.

    The difference becomes apparent when dealing with strict inequalities, for example.

    [eclipse 4]: reals([X]), X $> 5.
    X = X{5.0 .. 1.0Inf}
    Delayed goals:
            ic : (X{5.0 .. 1.0Inf} > 5)
    Yes (0.00s cpu)

    Note that the lower bound of X is still five despite the fact that X has been constrained to be strictly greater than five. Further note the presence of a delayed goal which will fail should X be constrained to be exactly five.

    [eclipse 5]: integers([X]), X $> 5.
    X = X{6 .. 1.0Inf}
    Yes (0.00s cpu)

    In this example since X is known to be integral, the lower bound of X can be set to 6, as there are no integers between five and six.

Previous Up Next