Re: [eclipse-clp-users] eclipse stuck at a simple problem

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,
-- Joachim