Soheil Samii wrote: > 1. The variable ordering is important. > 2. The value ordering is important (as we use _incomplete_ search). > These two issues can be solved by using search/6 instead of labeling/1 above. > There you can choose different orderings and different types of incomplete > search. Yes, both are important (also if you use a complete search), and I agree with Christoforidis Nikos that you should use your own search (BTW, I disagree on the fact that all NP-hard problems should be addressed with an incomplete search). One that sometimes works in scheduling is imposing precedence constraints between activities that should not overlap. For instance, you have 3 activities that should not overlap, with start times S1, S2 and S3 (ranging in 0..10) and durations D1=5, D2=6 and D3=7. You select the first variable (S1) and assign it its lowest value: S1=0. In backtracking, would you ever try S1=1? I suppose not, since there is no other activity that would fit before S1. So, one way is to impose S1+D1<S2, and in backtracking S2+D2<S1. > 3. The order of the constraints is important. No, this can give only a marginal improvement > Is it in general good for the performance to add constraints? It is difficult to say. There is a vast literature on redundant constraints, they often can improve performance, but you should check that they are redundant only logically, not propagation-wise. If you add a redundant constraint that removes values that are already removed by some other constraint, that would be useless. > How much does the cost function affect the performance? I'm a little bit > worried that my cost function (which I described in the beginning of this > email) makes the runtime to grow, but I don't know how to check that. The objective function can change the performance. For example, in CLP(FD) the summation constraints have very weak propagation. If you are undecided whether minimizing f1+f2 or max(f1,f2), the second would be much more efficient (but, of course, the result is different). Cheers, Marco -- Marco Gavanelli, Ph.D. in Computer Science Dept of Engineering University of Ferrara Via Saragat 1 - 44100 Ferrara (Italy) Tel +39-0532-97-4833 Fax +39-0532-97-4870 http://www.ing.unife.it/docenti/MarcoGavanelli/Received on Wed Jun 18 2008 - 00:50:55 CEST
This archive was generated by hypermail 2.3.0 : Tue Apr 16 2024 - 09:13:20 CEST