Re: "constructive" constraint programming

Dear Uli,

Various extensions have been proposed for the CSP and for Constraint 
Programming, in order to make them more "dynamic". As you said, in the 
basic CSP, everything is fixed: variables, constraints, domains; the 
various extensions try to make the framework more dynamic from these three
 viewpoints. One framework was proposed by Dechter and Dechter:

@InProceedings{DCSP-Dechter,
   author =       "R.~Dechter and A.~Dechter",
   title =        "Belief Maintenance in Dynamic Constraint Networks",
pages =        "37--42",
   ISBN =         "0-929280-00-8",
   editor =       "Tom M. {Smith, Reid G.; Mitchell}",
   booktitle =    "Proceedings of the 7th National Conference on
                  Artificial Intelligence",
   address =      "St. Paul, MN",
   month =        aug,
   year =         "1988",
   publisher =    "Morgan Kaufmann",
}

In this framework, they basically consider dynamicity on the set of 
constraints. Constraints can be added (as you can do also in Constraint 
Programming), and also removed from the constraint solver (this is less 
trivial). In a sense, you can also change domains, in a limited way: the 
set of possible values in a domain is fixed, but you can add and remove 
values by removing/adding constraints.

If you need more dynamicity on the set of domain values, and you need to 
add previously unknown values (i.e., you do not know the set of elements 
that could be in your domain), then you can have a look to the work by 
Mailharro (in ILOG Configurator)

@article{DomWildcard,
    author =  {D. Mailharro},
    title =   {A classification and constraint-based framework for
configuration},
    journal = {Artificial Intelligence for Engineering Design, Analysis and
Manufacturing},
    volume =  {12},
    pages =   {383-397},
    year =    1998,
}

and also to some of our works (implemented in ECLiPSe):

@ARTICLE{NGC2001,
   author =       "Rita Cucchiara and Marco Gavanelli and Evelina Lamma and
Paola Mello and Michela Milano and Massimo Piccardi",
   title =        "From Eager to Lazy Constrained Data Acquisition: A
General Framework",
   journal =      "New Generation Computing",
   year =         "2001",
   volume =       "19",
   number =       "4",
   month =        "Aug",
   pages =        {339--367},
   keywords =     "Constraint Satisfaction, Domain Acquisition,
                   Lazy Evaluation, Search Algorithms, Visual Search.",
   issn = "0288-3635",
}

@InProceedings{IJCAI99,
   author =       "Rita Cucchiara and Marco Gavanelli and Evelina Lamma and
Paola Mello
    and Michela Milano and Massimo Piccardi",
   title =        "Constraint Propagation and Value Acquisition: why we
should do it Interactively",
   booktitle =    "Proceedings of the Sixteenth International Joint
Conference on Artificial Intelligence",
   year =         "1999",
   month =        Jul # " 31 -- " # Aug # " 6",
   address =      "Stockholm, Sweden",
   pages =        "468--477",
   editor =       "Thomas Dean",
   publisher =    "Morgan Kaufmann",
   isbn = "1-55860-613-0",
}

@InProceedings{FroCoS2002,
   author =       "Marco Gavanelli and Evelina Lamma and Paola Mello and
Michela Milano",
   title =        "Exploiting constraints for domain managing in
{CLP(FD)}", booktitle =    "4th International Workshop on Frontiers of
Combining
Systems - FroCoS'2002",
   year =         "2002",
   month =        Apr # " 8-10",
   address =      "Santa Margherita Ligure, Italy",
   publisher =    "Springer Verlag",
   editor = "Alessandro Armando",
   series =       "Lecture Notes in Artificial Intelligence",
   volume =       "2309",
   url = "http://www.mrg.dist.unige.it/events/frocos2002/main.html", html =
"http://springerlink.metapress.com/app/home/contribution.asp?wasp=9c59kc0qwm4wpwd1ducy&referrer=parent&backto=issue,14,19;journal,763,1620;linkingpublicationresults,1:105633,1",
   pages =   {177-191},
  }

Our framework has also been applied to planning:

@inproceedings{DBLP:conf/ecp/BarruffiLMM99,
   author    = {Rosy Barruffi and
                Evelina Lamma and
                Paola Mello and
                Michela Milano},
   title     = {Least Commitment on Variable Binding in Presence of
Incomplete
                Knowledge.},
   booktitle = {ECP},
   year      = {1999},
   pages     = {159-171},
   crossref  = {conf/ecp/1999},
   bibsource = {DBLP, http://dblp.uni-trier.de}
}

Concerning dynamicity on the variables, I know of the following work:

@inProceedings{DCSP,
     author=     {S. Mittal and B. Falkenhainer},
     title=      {Dynamic Constraint Satisfaction Problems},
     booktitle = {Proc. of AAAI-90},
     pages =     {25-32},
     year={1990},
}

I hope these pointers can be useful to you (maybe I did not understand 
correctly your problem). I am very interested in your work, so, please, 
keep me informed of your developments!

Cheers,
Marco

At 10:07 23/12/2004, you wrote:

>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
>solution.
>
>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.
>
>Uli
>
>
>PS. I will post this question to comp.constraints, too.  I apologize if
you read it twice.
>--
>Ulrich Scholz
>
>scholz@informatik.tu-darmstadt.de
>http://www.intellektik.informatik.tu-darmstadt.de/~scholz

:-
Marco Gavanelli, Ph.D.
Computer Science Division
Dipartimento di Ingegneria
University of Ferrara
Via Saragat 1 - 44100 Ferrara (Italy)
Tel  +39-0532-97-4806
Fax  +39-0532-97-4870
http://www.ing.unife.it/docenti/MarcoGavanelli/
:-