Re: Eclipse and complexity

Hi Cristina,

On Fri, Apr 29, 2005 at 12:16:17PM +0200, Cristina Marconcini wrote:
> Dear All,
> 
> we use ECLIPSE to solve equations with  constraints on integer and 
> boolean variables,
> exploiting the /ic/ library.
> An example of the implemented equations is:
> 
> X1 :: -67108864..67108863 , X2 :: -67108864..67108863 , X3 :: 0..1, 
> (neg(X1 #= 5)) and (X1 #< X2) and (neg(X3 #= 0)) ,
> 
> So, that is the complexity for the algorithm applied by the
> solver to get a solution for the equation?

This is not an easy question to answer, for several reasons.

First, the answer will depend on precisely which class of constraints you're
interested in, and you don't make it clear in your email which class this
is.  For example, a straightforward conjunction of simple constraints with
no more than two variables where the coefficients of the variables are 1 or
-1 will give you one answer; allowing disjunction, or allowing more than two
variables, or allowing non-unit coefficients will change the answer (if for
no other reason than that the satisfiability problem for the first class of
constraints is in P; for the rest it is NP-hard, so for all known algorithms
the worst case complexity is at least exponential in the size of the input).

Second, for all but the most simple cases, the best one will be able to do
is give a very loose bound which may not be at all indicative of the true
performance of the solver (e.g. the simplex algorithm has exponential
complexity in the worst case, but in practice is polynomial except for
artificial examples).

Third, even for extremely simple cases, the behaviour can depend critically
on small details of the implementation of the constraint scheduler or the
order in which the constraints are posted.  (Examples are given in Mark
Wallace, Joachim Schimpf, Kish Shen and Warwick Harvey, 'On Benchmarking
Constraint Logic Programming Platforms.  Response to Fernandez and Hill's "A
Comparative Study of Eight Constraint Programming Languages over the Boolean
and Finite Domains."', Constraints: An International Journal, 9(1):5-34,
2004.)

> However is there in a better solver that we can adopt to solve our 
> problems?

Again, without knowing more about which class of problems you're trying to
solve, we cannot give advice on this.

Cheers,
Warwick