From: <wh_at_icparc.ic.ac.uk>

Date: Fri 29 Apr 2005 03:10:52 PM GMT

Message-ID: <20050429151052.GC10995@tempest.icparc.ic.ac.uk>

Date: Fri 29 Apr 2005 03:10:52 PM GMT

Message-ID: <20050429151052.GC10995@tempest.icparc.ic.ac.uk>

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, WarwickReceived on Fri Apr 29 16:13:13 2005

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:36 PM GMT GMT
*