From: Joachim Schimpf <joachim.schimpf_at_infotech.monash.edu.au>

Date: Fri, 25 Sep 2009 21:54:15 +1000

Date: Fri, 25 Sep 2009 21:54:15 +1000

Yu Liu wrote: > Dear all, > > I use eclipse because I think it should be faster than exhaustive > search. However, it turns out to be slower. ECLiPSe is not a black box solver, but a programming language with powerful primitives. Exhaustive search is an algorithm. I suppose your question is whether you can have an ECLiPSe solution that runs faster than an exhaustive search in something like C++ ? This will depend both on properties of your problem, and on how you implement it in ECLiPSe (the constraints you choose to model it, the search heuristics, the solver libraries you use, etc). Ultimately, constraint programs in ECLiPSe also rely on an exhaustive search algorithm, but the hope is that the search space can be cut down dramatically by the actions of constraint propagation. If your problem does not have strong constraints that cut down the search space, or if they are expressed in such a way (e.g. decomposition) that they don't propagate well, then there will be not enough pruning, and solving will be slower than with a naive approach. > Attached are my test > files. My problem takes exponential time. But for this small input, > exhaustive search takes only seconds. However, it seems to take > eclipse forever to solve the same problem. I am thinking whether I > should abandon eclipse for my project. Any suggestion is appreciated. In your model you have 5 decision variables F1 to F5, each of which can take 8 values [6000,8000,10000,12000,14000,16000,18000,21000]. That gives an (exhaustive) search tree with 5 levels, and 8 children on every node, resulting in 32768 leaves. You have also a cost variable Se, on which you perform branch-and-bound. Without pruning, you have to visit every leaf of the search tree. But with constraint propagation, we hope to discover half way down the tree, that certain subtrees are no longer feasible and we don't need to search them at all. For example, we would like to discover at level 2, when F1 and F2 have already been instantiated, that certain values for F3..F5 are no longer possible. In Eclipse, this means that the domains of F3..F5 should be reduced by the constraints, making the sub-trees smaller. The current cost bound, e.g. Se $=< 45000, would ideally also reduce these domains via propagation. However, if I try this in your model, I don't see any such domain reduction. I do not have time to investigate in detail, but I think the main problem is that your model is numerically quite badly conditioned and mixes numbers of hugely different magnitudes. For example your last constraint, which calculates the cost variable Se, looks like: -18300000000000 * _949965{0.0 .. 7.7210800000000033e-10} - 12800000000000 * _950262{0.0 .. 7.7210800000000033e-10} - 11100000000000 * _950559{0.0 .. 7.7210800000000033e-10} - 2800000000000 * _950856{0.0 .. 7.7210800000000033e-10} - 15200000000000 * _951153{0.0 .. 7.7210800000000033e-10} - 1000000 * _945704{0.0 .. 0.013594966021670154} - 1000000 * _946697{0.0 .. 0.0095090472719878676} - 1000000 * _947690{0.0 .. 0.0082461269311769787} - 1000000 * _948683{0.0 .. 0.0020801040907473464} - 1000000 * _949676{0.0 .. 0.011291993635485593} + Se{0.0 .. 45000.0} $= 0 Because of the huge differences in coefficients, bound changes on the cost variable do not cause much propagation back to the other variables, and so do not help in reducing search. Many other constraints look similar to this one: _949965{0.0 .. 7.7210800000000033e-10} $= _949820{0.0 .. 5.7620000000000014e-10} * _195{0.0 .. 1.34} The magnitudes of the bounds are so small that they are below the threshold under which lib(ic)'s interval propagation will stop propagating. You can change this threshold (set_threshold/1), but it applies uniformly to all variables, so your models will work better if the variables range over similar magnitudes. Another point I noticed is that you should give bounds to your variables whenever you know them, e.g. I added to your model: MaxV is max(Voltage), Vs $:: 0.0..MaxV, If you don't do that, the variables will start with domains of -inf..+inf, and infinite bounds don't propagate. These are some observations, but unfortunately I cannot really answer the question whether ECLiPSe is the right tool for your application. If you can spare the time, you may want to look at the material at http://4c.ucc.ie/~hsimonis/ELearning/index.htm which explains search space reduction very nicely, although there is not much about continuous nonlinear constraints. All the best, -- JoachimReceived on Fri Sep 25 2009 - 11:54:28 CEST

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