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

Hi!

I have some general questions related to optimization with ECLiPSe (or CLP in 
general). The problem that I try to solve with ECLiPSe is a task scheduling 
problem for multiprocessor system with a cost function that is a sum of a 
linear function in the optimization variables and the square-root of a 
quadratic function.

The CLP code is basically organized as follows:
* Declaring the domains of the variables (integer intervals).
* Linear constraints (precedence constraints, etc.).
* Resource constraints (using cumulative/4, which have three different 
versions in the libraries ic_cumulative, ic_edge_finder, and 
ic_edge_finder3).
* Declaring the cost function 'Cost'.
* Minimization using bb_min/3 in the library branch_and_bound, i.e., 
bb_min(labeling(StartTimes), Cost, Options).

For a reasonably average-size problem (40 variables) it takes incredibly long 
time to solve (after many hours it still hasn't found the optimum). I guess 
that it is because I use complete search and because I use the labeling/1 
predicate for the variable and value ordering. Is this true?

In my case, I want to use ECLiPSe as a heuristic to find a suboptimal 
schedule, because the ECLiPSe solver will be used inside another optimization 
loop. Therefore, I want the CLP solving process to be fast, and I have been 
reading and thinking about different ways to use ECLiPSe as a heuristic. 
These are the things that I have thought of:

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.

3. The order of the constraints is important.

4. bb_min/3 has options that, for example, lets the branch-and-bound cut away 
some solutions from the search tree. For example, there is an 
option 'factor': if 'factor'=0.9 it means that when the search engine tries 
to find a better solution than the current one, it tries to find a 10% better 
solution; thus, the obtained solution is guaranteed to be at most 10% from 
the optimum.

What are your experiences with heuristic optimization in ECLiPSe? Which of the 
abovementioned points affect the runtime the most, and is any of them not 
important for the runtime? Are there any other issues that I have forgot to 
look at to obtain an efficient heuristic with ECLiPSe?

Regarding the cumulative/4 constraint: Is it better to use the version in 
ic_cumulative or is it better to use the one in ic_edge_finder3? Which one is 
best from the point of view of runtime?

Is it in general good for the performance to add constraints?

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.

Has anyone used ECLiPSe for heuristic optimization to obtain results within 
fractions of a second, or is it totally unrealistic to achieve this?

Thankful for comments,

Regards,
/Soheil