From: Kish Shen <kisshen_at_cisco.com>

Date: Sun, 23 Mar 2008 20:03:36 +0000

Date: Sun, 23 Mar 2008 20:03:36 +0000

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 >Received on Sun Mar 23 2008 - 20:03:46 CET

*
This archive was generated by hypermail 2.2.0
: Thu Feb 02 2012 - 02:31:58 CET
*