[ANN] constraint-0.2

[Alexandre Fayolle]

Terry Reedy a écrit :
> To paraphrase Magnus Lie Hetland, the general constraint-propagation
> system constraint-0.2 takes 100 times as long to do the 8-queens
> problem as the specific backtracking queens.py found in the standard
> Python distribution: 15 versus .1 sec on comparable machines.

Yup. But we do mean to make it faster.

> The is about the same comparison, for some computations, as between
> generic/dynamic Python and type-specific C.  In both cases, there are
> two more questions of practical interest:  which platform/method is
> faster for the *programmer*?  and, is the slow method fast enough?

This is a good point.
Using the constraint package for 8 queens is very easy, since all you
have to do is describe the problem in terms of variable and constraints,
and call Solver().solve(Repository(variables,domains,constraints))

Is it fast enough? Well, it really depends. The good point in the
situation at hand is that I have not yet started thinking about
optimizing the code. There are other things to deal with first (adding
other kind of domains, such as finite sets, and the basic constraints
that go with these domains), so my personal answer is that it is for 
now fast enough as far as I'm concerned. Which does not mean it's ready
for production use. Hey, this is version 0.2!

> So, what is the relative programming speed of the general constraint
> propagation system versus specific backtracking?  I suspect that some
> people could whip up something like queens.py as fast or faster that
> they could the (unpublished?) constraint input for the same problem.

O(N) algorithm available for N queens has been published and proven to
be of minimal complexity, and will always be faster than a constraint
propagation approach which needs to consider N*(N-1) constraints, and
therefore will always have a complexity > O(N^2)

> However, I also suspect the reverse would be true for the more
> realistic and useful scheduling example that Fayolle used to
> illustrate and motivate constraint-0.2.
> http://www.logilab.org/python-logic/documentation.html

N-Queens is a well known problem, and it can be used as a benchmark for
solvers. Same for SEND+MORE=MONEY, which is also in the examples
directory of the constraint module. Since these problems are both well
known and simple in their expression, they can give an idea of the
relative performance of solvers. 

The scheduling example on the web page is completely made up, and its
purpose is to give a more "real-life" flavour to the tutorial. There are
many other constraint satisfaction problems that can be solved with the
module, or the the constraint module will be able to solve in the near
future (how to select tunes from a CD to best fill up a tape, how to
arrange your furniture in the flat you're going to move in, finding
a new password that you'll be able to easily memorize while
passing through the devious filters set up by your sysadmin, choosing
which fruits and vegetables to buy in the market in order not to eat the
same same thing every week...)

> Real world problems may have no solution as given.  On the other hand,
> constraints may not be absolute.  In the scheduling example, two
> workshops *can* be scheduled simultaneously, if necessary, even though
> many people want to take both.  So a stepwise procedure may be needed.
> (Given multiple solutions, one might also want to add 'wishes' as
> pseudoconstraints to help select just one.)  So, is it equally easy,
> with the two approaches, to add or drop constraints and rerun?  This
> would be fairly simple with c-0.2 input but probably harder for
> backtracking code unless planned for from the beginning.  Is it
> equally easy to give constraints priorities and have the system
> automatically either add them in order from the highest or drop them
> from lowest?  Constraint-0.2 evaluates constraints in the order
> listed, but I do not know if  it properly backtracks from failure to
> report the most satisfying solutions.

The short answer is no, because solving overconstrained problems is a
tricky thing. 

The longer answer is that you could quite easily build on top of
the constraint package an engine which would try to relax constraints
when no solution can be found. When finite set domains are implemented
in the solver, building this engine will be possible with the constraint
package itself. But this approach will not be as efficient as a
dedicated overconstrained package solver. 

Now, a little annecdote: when writing the scheduling example, the
first set of constraints I had come up with gave 1152 possible solution,
which I found was too many. So I did exactly what you suggested, I added
more constraints (this was really easy because adding a consrtaint is a
one-liner), twiddled with the choice of the non-simultaneous
conferences, until I found a combination which gave "only" 64 possible
solutions. It took me about 20 runs to get this, which was fairly quick
because the conference.py script runs in about 2 seconds on my machine. 


Alexandre Fayolle
-- 
LOGILAB, Paris (France).
http://www.logilab.com   http://www.logilab.fr  http://www.logilab.org
Narval, the first software agent available as free software (GPL).