NDLI: Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Please wait, while we are loading the content...

Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Content Provider	Springer Nature Link
Author	Georget, Yan Codognet, Philippe Rossi, Francesca
Copyright Year	1999
Abstract	Constraint retraction can be described, in general, as the possibility of deleting a previously stated piece of information. This is obviously very convenient in many programming frameworks, especially in those that involve some level of interaction between the user and the system, or also in those concerning rescheduling or replanning. Nevertheless, constraint retraction is usually not provided in current constraint programming environments. This is mainly due to its high complexity and also to its non-monotonic nature, which would make most of such systems much more complex to reason with. In this paper we avoid these problems by considering a specific constraint programming framework, called clpFD, that is, constraint logic programming (CLP) over finite domain (FD) constraints. We propose an algorithm which deletes a constraint from a set of FD constraints, while maintaining partial arc-consistency, which is usual in this programming framework. What is crucial is that the retraction operation we propose is incremental, in that it follows the chain of dependencies among variables which are set by the nature of the FD constraints, and by doing so it updates only the part of the constraint set which is affected by the deletion. We also detail how constraint retraction can be incorporated in the FD constraint solver and we evaluate its behavior within the clpFD system. Experimental results on usual benchmarks, on classes of problems of increasing connectivity, and also on a real-life problem show that in almost all cases the use of our retraction algorithm provides great speed-up with respect to standard methods while not slowing down the clpFD system when no retraction is performed. This provides the system with an efficient way of retracting constraints while not changing its performance when the user does not want to use this new feature.
Starting Page	5
Ending Page	42
Page Count	38
File Format	PDF
ISSN	13837133
Journal	Constraints
Volume Number	4
Issue Number	1
e-ISSN	15729354
Language	English
Publisher	Kluwer Academic Publishers
Publisher Date	1999-01-01
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Artificial Intelligence (incl. Robotics) Optimization Operation Research/Decision Theory
Content Type	Text
Resource Type	Article
Subject	Discrete Mathematics and Combinatorics Artificial Intelligence Computational Theory and Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Value Constraints in the CLP Scheme

Constraint-Based Facial Animation

Constraint Programming: Strategic Directions

Weighted Constraint Aggregation in Fuzzy Optimization

Towards a Constraint-Based Engineering Framework for Algorithm Design and Application

Improving Linear Constraint Propagation by Changing Constraint Representation

Probabilistic constraint reasoning

Special Issue on Constraint Agents

Some Challenges for Constraint Programming

Constraint Retraction in CLP(FD): Formal Framework and Performance Results

Similar Documents

Value Constraints in the CLP Scheme

Constraint-Based Facial Animation

Constraint Programming: Strategic Directions

Weighted Constraint Aggregation in Fuzzy Optimization

Towards a Constraint-Based Engineering Framework for Algorithm Design and Application

Improving Linear Constraint Propagation by Changing Constraint Representation

Probabilistic constraint reasoning

Special Issue on Constraint Agents

Some Challenges for Constraint Programming

Constraint Retraction in CLP(FD): Formal Framework and Performance Results