Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-05T11:38:44.873Z Has data issue: false hasContentIssue false
  • English
  • Français

About the choice of the variable to unassign in a decision repair algorithm

Published online by Cambridge University Press:  15 July 2005

Cédric Pralet  and
Gérard Verfaillie
Cédric Pralet
Affiliation:
LAAS-CNRS, Toulouse, France; [email protected]; [email protected]
Gérard Verfaillie
Affiliation:
LAAS-CNRS, Toulouse, France; [email protected]; [email protected]
Get access

Abstract

The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45),which has been designed to solve constraint satisfaction problems (CSP), canbe seen, either (i) as an extension of the classical depth first treesearch algorithm with the introduction of a free choice of the variable towhich to backtrack in case of inconsistency, or (ii) as a localsearch algorithm in the space of the partial consistent variableassignments. or (iii) as a hybridisation between local searchand constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of thevariable to which to backtrack behave well on consistent instances andthat other heuristics behave well on inconsistent ones. They show alsothat, despite its a priori incompleteness, decision repair,equipped with some specific heuristics, can solve within a limited timealmost all the consistent and inconsistent randomly generatedinstances over the whole constrainedness spectrum. In this paper, wediscuss the heuristics that could be used by decisionrepair to solve consistent instances, on the one hand, andinconsistent ones, on the other hand. Moreover, we establish thatsome specific heuristics make decision repair complete.

Keywords

Constraint satisfaction problemdepth first treesearchlocal searchconstraint propagationbacktrackheuristicscompleteness.
Type
Research Article
Information
RAIRO - Operations Research , Volume 39 , Issue 1 , January 2005 , pp. 55 - 74
Copyright
© EDP Sciences, 2005

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

E. Aarts and J. Lenstra, Eds. Local Search in Combinatorial Optimization. John Wiley & Sons (1997).
C. Bessière and J.C. Régin, MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?), in Proc. of the 2nd International Conference on Principles and Practice of Constraint Programming (CP-96)). Cambridge, MA, USA. Lect. Notes Comput. Sci. (1996) 61–75.
C. Bliek, Generalizing Partial Order and Dynamic Backtracking, in Proc. of the 15th National Conference on Artificial Intelligence (AAAI-98). Madison, WI, USA (1998) 319–325.
R. Dechter and R. Mateescu, Mixtures of Deterministic-Probabilistic Networks and their AND/OR Search Space, in Proc. of the 20th International Conference on Uncertainty in Artificial Intelligence (UAI-04). Banff, Canada (2004).
Ginsberg, M., Dynamic Backtracking. J. Artif. Intell. Res. 1 (1993) 25–46.
M. Ginsberg and D. McAllester, GSAT and Dynamic Backtracking, in Proc. of the 4th International Conference on the Principles of Knowledge Representation and Reasoning (KR-94). Bonn, Germany (1994) 226–237.
C. Gomes and B. Selman, Problem Structure in the Presence of Perturbations, in Proc. of the 14th National Conference on Artificial Intelligence (AAAI-97). Providence, RI, USA (1997).
Jussien, N. and Lhomme, O., Local Search with Constraint Propagation and Conflict-based Heuristics. Artif. Intell. 139 (2002) 21–45. CrossRef
A. Mackworth, Constraint Satisfaction, in Encyclopedia of Artificial Intelligence, S. Shapiro, Ed. John Wiley & Sons (1992) 285–293.
C. Pralet and G. Verfailllie, Travelling in the World of Local Searches in the Space of Partial Assignments, in Proc. of the International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimisation Problems (CP-AI-OR-04). Nice, France (2004) 240–255.
Prestwich, S., Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search. Ann. Oper. Res. 115 (2002) 51–72. CrossRef
Prosser, P., Hybrid Algorithms for the Constraint Satisfaction Problems. Comput. Intell. 9 (1993) 268–299. CrossRef