Re: [eclipse-clp-users] How to extend lib(ic) to get stronger propagation?

Ulrich Scholz wrote:
> It is clear that a constraint package cannot detect and propagate all
> possible simplifications.  But sometimes, a specific simplification can be
> of great help.
> 
> Consider the following constraint program.
> 
>   [eclipse 3]: lib(ic), [A, B] :: [0, 100], A #=< B, B #=< A.
> 
>   A = A{[0, 100]}
>   B = B{[0, 100]}
> 
> 
>   Delayed goals:
>           -(B{[0, 100]}) + A{[0, 100]} #=< 0
>           B{[0, 100]} - A{[0, 100]} #=< 0
>   Yes (0.00s cpu)
> 
> 
> It would really help me if (an extended) ic would simplify this case to
> A#=B.  Labeling is no option for me, I need to detect this case early.
> 
This is a well known weakness with local propagation based solvers like 
ic, that you cannot perform `global' reasoning *between* constraints. It 
certainly does not make sense to try to extend ic itself to deal with 
some specific cases such as the one you show, firstly because it is far 
from general, and secondly, even for the special cases, the cost is 
prohibitive.

If your application has specific special cases like the one you 
outlined, and you think the cost for doing checks is worthwhile in your 
specific application, then you should write your own code to deal with 
this, as suggested by Helmut.

A more general approach is to try a hybrid approach -- using different 
solvers to tackle the same problem, exploiting the different strengths 
of the different solvers. This has been a big research area, and is one 
reason why a lot of development effort of the ECLiPSe team have been 
devoted to developing the eplex library.

 >I know CHR and use it for some constraints.  But re-writing lib(ic) >with
 >CHRs will be my last resort because it is a lot of work for some small 
 >extra
 >propagation.  And most likely lib(ic) is more correct and more >efficient.

 >I don't know how to add an extension to lib(ic) with CHRs, e.g., how to
 >trigger a CHR in case two ic constraints are posted.

Using CHR (lib(ech)) as Helmut suggested is probably the simplest 
approach by far. I am not sure I understand your difficulties completely 
-- the idea is to post the same  constraint to both CHR and ic, i.e. you 
define something like:

my_gte(X,Y) :-
    ic: (X #>= Y),
    chr_gte(X,Y).


you then write some CHR rules like:

chr_gte(X,Y), chr_lte(X,Y) <=> ic: (X #= Y).


If you try to do this with ic alone (i.e. writing your own special 
constraint), you will need to write your own mechanism for storing 
posted constraints, search them for matches, i.e. redoing what is 
implemented by the CHR library already.

Cheers,

Kish

-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.