Re: [eclipse-clp-users] Performance-related issues in heuristic optimization with ECLiPSe

From: Marco Gavanelli <marco.gavanelli_at_unife.it>
Date: Wed, 18 Jun 2008 09:49:10 +0200
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.2.0 : Thu Feb 02 2012 - 02:31:58 CET