From: Soheil Samii <sohsa_at_ida.liu.se>

Date: Tue, 17 Jun 2008 17:43:43 +0200

Date: Tue, 17 Jun 2008 17:43:43 +0200

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, /SoheilReceived on Tue Jun 17 2008 - 08:42:18 CEST

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