Re: [eclipse-users] Speed Up Constraint Imposing Time in ECLiPSe

Hi David,

If the time to impose constraints is not growing linearly with the 
number of constraints, it seems likely that as each constraint is 
imposed, you are spending more and more time in propagation due to the 
added constraint. Normally, this sort of propagation should help narrow 
the domains of your variables, but it may be that in your case, this is 
not helping much, but is imposing a high computational cost. You can 
avoid any propagation as you impose your constraints by imposing the 
constraints at a higher priority than the priority of the propagation.
You can call the loop in which you impose your constraints inside a 
call_priority/2:

        call_priority(impose_constraints(Cs), <N>)

where <N> is a sufficiently high priority -- 2 should be high enough.

The priority system is not very nice, because it is global, and in the 
case above, you need to know the priority you are using is higher than 
those use by ic internally. We have not really found a good way to solve 
all the issues surrounding this.

Doing this, the propagation will only happen once you have imposed all 
your constraints. This is now likely to become more expensive than 
before, but it may be cheaper than the sum of all the smaller 
propagations you have done previously -- it all depends on your problem.

If your problem is indeed due to this propagation as you impose your 
constraints, you may want to look at exactly what is being propagated, 
and if you can reorder your constraints to minimise this -- this would 
be a cleaner solution than using call_priority/2, but of course your 
constraint propagation may be too complex for you to fully understand it.

We had a paper in which we studied the behaviour of ordering the posting 
of constraints (in the context of benchmarking and its problems) for a 
very simple set of constraints:

On Benchmarking Constraint Logic Programming Platforms. Response to 
Fernandez and Hill's "A Comparative Study of Eight Constraint 
Programming Languages over the Boolean and Finite Domains"
    by Mark Wallace, Joachim Schimpf, Kish Shen and Warwick Harvey. In 
CONSTRAINTS Journal, ed. E.C. Freuder,9(1), pp 5-34, Kluwer, 2004.

This paper is listed in http://www.eclipse-clp.org/reports/index.html, 
but there is no link to a downloadable version of the paper. I don't 
know if this is because of copyright issues, but if you are interested 
in the paper, and cannot get hold of the Constraints journal,  contact 
me again.

Cheers,

Kish

David Tian wrote:
> Hi,
>
> My problem is a data mining problem (a discretization problem) and I
> modelled it as a constraint satisfaction optimization problem (CSOP)  
> and implemented the CSOP using the ic library of ECLiPSe. For  
> different instances of problems, the CSP consists of different total  
> number of constraints. However, when the number of constraints  
> increases, the time to impose them goes increases rapidly. To impose  
> 28552 constraints, it takes 261.70 seconds. There can be large  
> problems with more constraints than this problem, this makes my CSOP  
> inefficient.
>
> I imposed all the constraints one by one using a loop. I am wondering  
> if there is another way to impose the constraints in ECLiPSe to speed  
> up the constraint imposing time.
>
> For your interest, my paper describing the problem and CSOP is at:  
> http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4295437
>
> many thanks and regards,
>
> David
>
>
>
>
> _______________________________________________
> ECLiPSe-Users mailing list
> ECLiPSe-Users_at_crosscoreop.com
> http://www.crosscoreop.com/mailman/options/eclipse-users
>