"constructive" constraint programming

From: Ulrich Scholz <scholz_at_informatik.tu-darmstadt.de>
Date: Thu 23 Dec 2004 09:07:53 AM GMT
Message-ID: <20041223100753.A26022@informatik.tu-darmstadt.de>
Dear all,

I'm thinking of a constraint programming system that is more
"constructive" than the examples I see in literature.  But maybe I'm
mislead and there are lots of out there I don't know.  I would be
grateful for any links, pointers to literature, and comments.

By now I know CP the following way: There is a fixed number of
variables which represent the entities of a problem.  A fixed
procedure poses constraints on these variables that correspond to
relations between the entities.  Once all constraints are successfully
posted, the variables are labeled and the solution is extracted.  In case,
the program fails while posting the constraints or labeling the variables,
the program exits and reports that the problem has no

I call this approach "static" because the solution process is
programmed for one particular type of problem, regardless of the fact that
it is often possible to apply such solvers to problems of various sizes. 
They are still restricted to a specific class of problems and to a
specific way to solve them.

But many problems require a more constructive solution process: For
example in planning, it is not known beforehand how many actions there are
necessary to solve a problem.  Consequently, the number of
variables and their constraints is unknown, too.  Planning systems that
use constraints, e.g., non-linear (least-commitment) planning systems,
address this problem by constructing the constraint
satisfaction problem (aka partial plan) simultaneously with solving it. 
Failure then does not mean that the problem is unsolvable, just that the
current constraint satisfaction problem is constructed the wrong way: The
planning system backtracks and explores a different construction.

The system I plan to build has two inputs: (1) A problem (e.g., a
planning problem) and (2) a description how to construct constraint
satisfaction problems from such an input.

What do you think?  As I said, any comment welcome.


PS. I will post this question to comp.constraints, too.  I apologize if
you read it twice.
Ulrich Scholz

Received on Thu Dec 23 23:58:07 2004

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