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

Cédric Pralet; Gérard Verfaillie

RAIRO - Operations Research (2010)

  • Volume: 39, Issue: 1, page 55-74
  • ISSN: 0399-0559

Abstract

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

How to cite

top

Pralet, Cédric, and Verfaillie, Gérard. "About the choice of the variable to unassign in a decision repair algorithm." RAIRO - Operations Research 39.1 (2010): 55-74. <http://eudml.org/doc/105323>.

@article{Pralet2010,
abstract = { The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45), which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between local search and constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of the variable to which to backtrack behave well on consistent instances and that other heuristics behave well on inconsistent ones. They show also that, despite its a priori incompleteness, decision repair, equipped with some specific heuristics, can solve within a limited time almost all the consistent and inconsistent randomly generated instances over the whole constrainedness spectrum. In this paper, we discuss the heuristics that could be used by decision repair to solve consistent instances, on the one hand, and inconsistent ones, on the other hand. Moreover, we establish that some specific heuristics make decision repair complete. },
author = {Pralet, Cédric, Verfaillie, Gérard},
journal = {RAIRO - Operations Research},
keywords = {Constraint satisfaction problem; depth first tree search; local search; constraint propagation; backtrack; heuristics; completeness. ; depth first tree search; local search; completeness},
language = {eng},
month = {3},
number = {1},
pages = {55-74},
publisher = {EDP Sciences},
title = {About the choice of the variable to unassign in a decision repair algorithm},
url = {http://eudml.org/doc/105323},
volume = {39},
year = {2010},
}

TY - JOUR
AU - Pralet, Cédric
AU - Verfaillie, Gérard
TI - About the choice of the variable to unassign in a decision repair algorithm
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 39
IS - 1
SP - 55
EP - 74
AB - The decision repair algorithm (Jussien and Lhomme, Artificial Intelligence139 (2002) 21–45), which has been designed to solve constraint satisfaction problems (CSP), can be seen, either (i) as an extension of the classical depth first tree search algorithm with the introduction of a free choice of the variable to which to backtrack in case of inconsistency, or (ii) as a local search algorithm in the space of the partial consistent variable assignments. or (iii) as a hybridisation between local search and constraint propagation. Experiments reported in Pralet and Verfailllie (2004) show that some heuristics for the choice of the variable to which to backtrack behave well on consistent instances and that other heuristics behave well on inconsistent ones. They show also that, despite its a priori incompleteness, decision repair, equipped with some specific heuristics, can solve within a limited time almost all the consistent and inconsistent randomly generated instances over the whole constrainedness spectrum. In this paper, we discuss the heuristics that could be used by decision repair to solve consistent instances, on the one hand, and inconsistent ones, on the other hand. Moreover, we establish that some specific heuristics make decision repair complete.
LA - eng
KW - Constraint satisfaction problem; depth first tree search; local search; constraint propagation; backtrack; heuristics; completeness. ; depth first tree search; local search; completeness
UR - http://eudml.org/doc/105323
ER -

References

top
  1. E. Aarts and J. Lenstra, Eds. Local Search in Combinatorial Optimization. John Wiley & Sons (1997).  
  2. 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.  
  3. 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.  
  4. 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).  
  5. M. Ginsberg, Dynamic Backtracking. J. Artif. Intell. Res.1 (1993) 25–46.  
  6. 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.  
  7. 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).  
  8. N. Jussien and O. Lhomme, Local Search with Constraint Propagation and Conflict-based Heuristics. Artif. Intell.139 (2002) 21–45.  
  9. A. Mackworth, Constraint Satisfaction, in Encyclopedia of Artificial Intelligence, S. Shapiro, Ed. John Wiley & Sons (1992) 285–293.  
  10. 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.  
  11. S. Prestwich, Combining the Scalability of Local Search with the Pruning Techniques of Systematic Search. Ann. Oper. Res.115 (2002) 51–72.  
  12. P. Prosser, Hybrid Algorithms for the Constraint Satisfaction Problems. Comput. Intell.9 (1993) 268–299.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.