自适应约束求解方法研究
|
摘要
约束求解是人工智能领域最热门的关键词之一，它是约束程序（ConstraintProgramming，CP）的核心问题。约束求解方法的发展为业界提供了许多机遇和挑战。当前，约束求解方法已经发展到一个新阶段，自适应约束求解方法正逐渐成为研究热点并引领着约束求解的发展方向。分支方式的选择、变量选择、值选择以及约束传播这些与约束求解密切相关的环节严重影响着约束求解的效率。实现上述环节上的自适应是研究自适应约束求解方法的新途径。
本文在概述约束满足问题的基本概念及约束求解过程之后，详述了在约束求解的各环节应用自适应理念的方法，这些环节包括分支方式的选择、变量选择、值选择以及约束传播，重点介绍了自适应对求解效率的提高程度。文章主要围绕着实现自适应约束求解的各种技术和方法展开研究，研究内容具体包括：（1）比较分析了典型分支策略，突出强调自适应分支策略的优势，从辅助顾问和值排序两个角度改进自适应分支策略，提出AdaptBranchLVO自适应分支求解算法，进而推出自适应分支选择约束求解方法；（2）通过对典型变量排序启发式的分析比较，实现自适应变量选择约束求解方法；（3）借助自适应值排序启发式，将自适应值选择与自适应分支结合，设计算法AdaptBranch~(surv)，进一步研究自适应值选择约束求解方法；（4）设计并实现自适应约束传播约束求解方法，包括基于比特位操作的自适应约束传播和基于AC与LmaxRPC的自适应约束传播这些两种约束传播方法之间的自适应，以及多种约束传播方法之间学习型自适应，提出算法AC_MaxRPC_Bitwise和ADAPT~(AC-LmaxRPC)。文中研究的自适应约束求解方法在不同程度上提升了求解效率，作用显著。此类方法的研究有助于从各个环节和层面提升自适应约束求解能力，实现约束求解的智能化。
The concept of constraint has been used and expanded to the areas of industry and livelihood.As the accelerating of global economy, the theory and application research in constraintprogramming has been paid more and more attention since it was proposed in the late1980s.Constraint programming can be used in industry, agriculture, communication, manufacture,transport, aviation etc. In these areas, constraint can be used in production scheduling, productconfiguration and human management which have actual sense and business values, inreverse, lay the foundation of the research of constraint programming.
Constraint satisfaction problem is a key problem of constraint programming, whosekernel is constraint solving. How to find a universally effective constraint solving method is asevere challenge of constraint programming. The traditional solving technology can bedivided as two kinds: search and inference. The deputy of the former is backtrackingalgorithm, and the main methods of the later are variable elimination, tree-decomposition andconsistency technology. With the development of constraint solving, the concept of “adaptive”has been focused on, which has gradually become a spotlight and guided the futuredevelopment. The adaptive constraint solving uses the empiric value which gets in self-searching to guide the following searching. More and more researches get to consider instructure information of problems, and propose some adaptive constraint solving methodswith more adaptability. These modified methods promote the efficiency and intelligence ofalgorithms, but the methods have more capacious development space.
The links which are closely related to constraint solving such as branching selection,variable selection, value selection and constraint propagation, etc. are connected with theefficiency of constraint solving seriously. There is no doubt that realizing adaptive in theselinks has become a new improvement way for adaptive constraint solving.
After summarizing the basic concepts of constraint and the process of constraint solving,the thesis mainly researches the technologies and methods of adaptive constraint solvingwhich focus on the process of constraint solving itself. These methods which use adaptiveidea are used in every link in constraint solving. We focus on the four kinds of methods:adaptive branching selection constraint solving methods, adaptive variable selectionconstraint solving methods, adaptive value selection constraint solving methods and adaptiveconstraint propagation constraint solving methods. The emphases of the research are thepromoting degree of solving efficiency by adaptation.
(1) Adaptive branching selection constraint solving methods: The effect andsignificance of adaptive branching selection to constraint solving are analysis. Based on introduction of existing branching selection strategies, the typical branch strategies arecompared, thus the advantage of adaptive branching strategy is highlighted. Two improvedadaptive branching strategies are proposed. One is the modified strategy of assistantconsultants heuristic, the other is a new adaptive branching solving algorithm:AdaptBranchLVO. After comparing other assistant consultants, the high efficiency of adaptivebranching strategy is proved. By testing multiple typical Benchmarks, the efficiency inconstraint solving of AdaptBranchLVOis validated. We get a result that importing the adaptivebranching strategy to constraint solving is an effective method to the efficiency of constraintsolving.
(2) Adaptive variable selection constraint solving methods: Based on the research andcomparison of variable ordering heuristics, the adaptive variable selection method inconstraint solving is proposed. The methods are different from the static or dynamic variableordering heuristics that only use the information of initial and current nodes, which use theinformation of every node from searching tree to help realize the adaptive variable orderingheuristics. By comparing the typical variable ordering heuristics, the idea of the generalizedadaptive variable selection constraint solving is proposed, and it lays the foundation ofcombining it with the adaptive constraint propagation in the later chapters.
(3) Aadaptive value selection constraint solving methods: Based on typical valueordering heuristics, the methods of adaptive value selection in constraint solving are discussed.The survivors-first learning adaptive value ordering heuristics are focused on. The methods ofsearching more hopeful values in propagation with low cost are introduced, and the values areused to speed up some special problem solving with the help of heuristics in order to achieveadaptive value selection constraint solving. Furthermore, drawing support from adaptive valueordering heuristics, it combines the adaptive value selection with the adaptive branchingselection. Algorithm AdaptBranchsurvis proposed, and the algorithm is tested to get efficiency.After comparing AdaptBranchsurvand AdaptBranchLVO, AdaptBranchsurvhas an apparentadvantage of improving the efficiency of constraint solving via the experimental result.
(4) Adaptive constraint propagation constraint solving methods: With the help ofdiscussing the importance of constraint propagation, the significance of adaptive constraintpropagation is proposed. The constraint solving methods of constraint propagation andadaptation are discussed. This section focuses on two kinds of methods: one is the adaptationbetween two constraint propagation methods, and the other is learning adaptation amongmultiple constraint propagation methods. The former discusses the adaptive constraintpropagation algorithm based on bitwise operations and the adaptive constraint propagationbased on AC and LmaxRPC. The modified algorithm AC_MaxRPC_Bitwise andADAPTAC-LmaxRPCare proposed. The efficiency of these algorithms is proved by Benchmarkstests. The latter realizes learning adaptive constraint propagation among multiple strategieswith the aids of LPP, which paves the way for further study. In the end, it proves the notableperformance of adaptive constraint propagation.
With the application of adaptive method to constraint solving, many results have beengotten. More and more teams focus on this area, and develop the area. Our adaptive constraintsolving methods improve the efficiency of constraint solving from a new perspective. Theseadaptive methods help constraint in many links and levels to improve constraint solving, andget more intelligent algorithm.
本文在概述约束满足问题的基本概念及约束求解过程之后，详述了在约束求解的各环节应用自适应理念的方法，这些环节包括分支方式的选择、变量选择、值选择以及约束传播，重点介绍了自适应对求解效率的提高程度。文章主要围绕着实现自适应约束求解的各种技术和方法展开研究，研究内容具体包括：（1）比较分析了典型分支策略，突出强调自适应分支策略的优势，从辅助顾问和值排序两个角度改进自适应分支策略，提出AdaptBranchLVO自适应分支求解算法，进而推出自适应分支选择约束求解方法；（2）通过对典型变量排序启发式的分析比较，实现自适应变量选择约束求解方法；（3）借助自适应值排序启发式，将自适应值选择与自适应分支结合，设计算法AdaptBranch~(surv)，进一步研究自适应值选择约束求解方法；（4）设计并实现自适应约束传播约束求解方法，包括基于比特位操作的自适应约束传播和基于AC与LmaxRPC的自适应约束传播这些两种约束传播方法之间的自适应，以及多种约束传播方法之间学习型自适应，提出算法AC_MaxRPC_Bitwise和ADAPT~(AC-LmaxRPC)。文中研究的自适应约束求解方法在不同程度上提升了求解效率，作用显著。此类方法的研究有助于从各个环节和层面提升自适应约束求解能力，实现约束求解的智能化。
The concept of constraint has been used and expanded to the areas of industry and livelihood.As the accelerating of global economy, the theory and application research in constraintprogramming has been paid more and more attention since it was proposed in the late1980s.Constraint programming can be used in industry, agriculture, communication, manufacture,transport, aviation etc. In these areas, constraint can be used in production scheduling, productconfiguration and human management which have actual sense and business values, inreverse, lay the foundation of the research of constraint programming.
Constraint satisfaction problem is a key problem of constraint programming, whosekernel is constraint solving. How to find a universally effective constraint solving method is asevere challenge of constraint programming. The traditional solving technology can bedivided as two kinds: search and inference. The deputy of the former is backtrackingalgorithm, and the main methods of the later are variable elimination, tree-decomposition andconsistency technology. With the development of constraint solving, the concept of “adaptive”has been focused on, which has gradually become a spotlight and guided the futuredevelopment. The adaptive constraint solving uses the empiric value which gets in self-searching to guide the following searching. More and more researches get to consider instructure information of problems, and propose some adaptive constraint solving methodswith more adaptability. These modified methods promote the efficiency and intelligence ofalgorithms, but the methods have more capacious development space.
The links which are closely related to constraint solving such as branching selection,variable selection, value selection and constraint propagation, etc. are connected with theefficiency of constraint solving seriously. There is no doubt that realizing adaptive in theselinks has become a new improvement way for adaptive constraint solving.
After summarizing the basic concepts of constraint and the process of constraint solving,the thesis mainly researches the technologies and methods of adaptive constraint solvingwhich focus on the process of constraint solving itself. These methods which use adaptiveidea are used in every link in constraint solving. We focus on the four kinds of methods:adaptive branching selection constraint solving methods, adaptive variable selectionconstraint solving methods, adaptive value selection constraint solving methods and adaptiveconstraint propagation constraint solving methods. The emphases of the research are thepromoting degree of solving efficiency by adaptation.
(1) Adaptive branching selection constraint solving methods: The effect andsignificance of adaptive branching selection to constraint solving are analysis. Based on introduction of existing branching selection strategies, the typical branch strategies arecompared, thus the advantage of adaptive branching strategy is highlighted. Two improvedadaptive branching strategies are proposed. One is the modified strategy of assistantconsultants heuristic, the other is a new adaptive branching solving algorithm:AdaptBranchLVO. After comparing other assistant consultants, the high efficiency of adaptivebranching strategy is proved. By testing multiple typical Benchmarks, the efficiency inconstraint solving of AdaptBranchLVOis validated. We get a result that importing the adaptivebranching strategy to constraint solving is an effective method to the efficiency of constraintsolving.
(2) Adaptive variable selection constraint solving methods: Based on the research andcomparison of variable ordering heuristics, the adaptive variable selection method inconstraint solving is proposed. The methods are different from the static or dynamic variableordering heuristics that only use the information of initial and current nodes, which use theinformation of every node from searching tree to help realize the adaptive variable orderingheuristics. By comparing the typical variable ordering heuristics, the idea of the generalizedadaptive variable selection constraint solving is proposed, and it lays the foundation ofcombining it with the adaptive constraint propagation in the later chapters.
(3) Aadaptive value selection constraint solving methods: Based on typical valueordering heuristics, the methods of adaptive value selection in constraint solving are discussed.The survivors-first learning adaptive value ordering heuristics are focused on. The methods ofsearching more hopeful values in propagation with low cost are introduced, and the values areused to speed up some special problem solving with the help of heuristics in order to achieveadaptive value selection constraint solving. Furthermore, drawing support from adaptive valueordering heuristics, it combines the adaptive value selection with the adaptive branchingselection. Algorithm AdaptBranchsurvis proposed, and the algorithm is tested to get efficiency.After comparing AdaptBranchsurvand AdaptBranchLVO, AdaptBranchsurvhas an apparentadvantage of improving the efficiency of constraint solving via the experimental result.
(4) Adaptive constraint propagation constraint solving methods: With the help ofdiscussing the importance of constraint propagation, the significance of adaptive constraintpropagation is proposed. The constraint solving methods of constraint propagation andadaptation are discussed. This section focuses on two kinds of methods: one is the adaptationbetween two constraint propagation methods, and the other is learning adaptation amongmultiple constraint propagation methods. The former discusses the adaptive constraintpropagation algorithm based on bitwise operations and the adaptive constraint propagationbased on AC and LmaxRPC. The modified algorithm AC_MaxRPC_Bitwise andADAPTAC-LmaxRPCare proposed. The efficiency of these algorithms is proved by Benchmarkstests. The latter realizes learning adaptive constraint propagation among multiple strategieswith the aids of LPP, which paves the way for further study. In the end, it proves the notableperformance of adaptive constraint propagation.
With the application of adaptive method to constraint solving, many results have beengotten. More and more teams focus on this area, and develop the area. Our adaptive constraintsolving methods improve the efficiency of constraint solving from a new perspective. Theseadaptive methods help constraint in many links and levels to improve constraint solving, andget more intelligent algorithm.
引文
[1]. Christophe Lecoutre. Constraint Networks: Techniques and Algorithms [M]. London, UK: WILEY,2009.
[2]. Francois Rossi, Peter van Beek, and Toby Walsh, editors. Handbook of Constraint Programming [M].Amsterdam, Netherland: Elsevier,2006.
[3]. Alan K.Mackworth and Eugene C.Freuder. The Complexity of some polynomial network consistencyalgorithms for constraint satisfaction problems [J]. Artificial Intelligence,1985,25:65–74.
[4]. Tsang Edward. Foundations of Constraint Satisfaction [M]. London:Academic Press,1993.
[5].刘春晖.基于约束传播的约束求解方法研究[D].长春：吉林大学博士论文,2008.
[6].王秦辉,陈恩红,王煦法.分布式约束满足问题研究及其进展[J].软件学报,2006,17(10):2029–2039.
[7].季晓慧,黄拙,张健.约束求解与优化技术的结合[J].计算机学报,2005,28(11):1790–1797.
[8]. Runming Lu, Sheng Liu and Jian Zhang. Searching for Doubly Self-Orthogonal Latin Squares [C]. InProceedings of cp–2011, Perugia, Italy, pages538–545,2011.
[9]. Ke Xu and Wei Li. Exact Phase Transitions in Random Constraint Satisfaction Problems [J]. Journalof Artificial Intelligence Research,12(2000):93–103.
[10]. Ke Xu and Wei Li. Many Hard Examples in Exact Phase Transitions [J]. Theoretical ComputerScience,355(2006):291–302.
[11]. Ke Xu, Frederic Boussemart, Fred Hemery and ChristopheLecoutre. Random Constraint Satisfaction:Easy Generation of Hard (Satisfiable) Instances [J]. Artificial Intelligence,2007,171(8–9):514–534.
[12].高健.基于推理的约束满足问题求解算法研究[D].长春：吉林大学硕士士论文,2008.
[13]. D. Cohen, P. Jeavons, P. Jonsson, and M. Koubarakis. Building tractable disjunctive constraints [J].Journal of the ACM,47(2000):826–853.
[14]. Rina Dechter. Constraint processing [M]. San Francisco: Morgan Kaufmann Publishers,2003.
[15]. Patrick Prosser. Hybrid algorithms for the constraint satisfaction problems [J]. ComputationalIntelligence,1993,9(3):268–299.
[16]. Matthew L. Ginsberg. Dynamic backtracking [J]. Artificial Intelligence,1993,(1):25–46.
[17]. Thanasis Balafoutis. Adaptive strategies for solving CSP [D]. Aegean, Greece: University of theAegean,2011.
[18]. J.E. Borrett, E.P.K. Tsang and N.R. Walsh. Adaptive constraint satisfaction [C]. In Proceedings of15thUK Planning and Scheduling Special Interest Group Workshop, Liverpool, UK,1996.
[19]. James E. Borrett and Edward P.K. Tsang. Adaptive constraint satisfaction: the quickest first principle[J]. Computational Intelligence: Collaboration, Fusion and Emergence, Intelligent Systems ReferenceLibrary,1(2009),203–230.
[20]. Susan L. Epstein, Eugene C. Freuder, Richard Wallace, Anton Morozov and Bruce Samuels. Theadaptive constraint engine [C]. In Proceedings of CP–2002, New York, USA, pages525–540,2002.
[21]. Frédéric Boussemart, Fred Heremy, Christophe Lecoutre, and Lakhdar Sais. Boosting SystematicSearch by Weighting Constraints [C]. In Proceedings of ECAI–2004, Valencia, Spain, pages482–486,2004.
[22]. Diarmuid Grimes and Richard J. Wallace. Sampling Strategies and Variable Selection in WeightedDegree Heuristics [C]. In Proceedings of CP–2007, Providence, USA, pages831–838,2007.
[23]. Deepak Mehta and M.R.C. van Dongen. Probabilistic Consistency Boosts MAC and SAC [C]. InProceedings of IJCAI–2007, Hyderabad, India, pages143–148,2007.
[24]. El Sakkout, Mark Wallace, and Barry Richards. An Instance of Adaptive Constraint Propagation [C].In Proceedings of CP–96, Cambridge MA, pages164–178,1996.
[25]. Eugene C. Freuder and Richard J. Wallace. Selective Relaxation for Constraint Satisfaction Problems[C]. In Proceedings of the Third International IEEE Computer Society Conference on Tools forArtificial Intelligence, San Jose, USA, pages332–339,1991.
[26]. Christian Schulte and Peter Stuckey. Speeding Up Constraint Propagation [C]. In Proceedings ofCP–2004, Toronto, Canada, pages619–633,2004.
[27]. Kostas Stergiou. Heuristics for Dynamically Adapting Propagation [C]. In Proceedings of ECAI–2008,Patras, Greece, pages485–489,2008.
[28]. Thanasis Balafoutis and Kostas Stergiou. Adaptive Branching for Constraint Satisfaction Problems[C]. In Proceedings of ECAI–2010, Lisbon, Portugal, pages855–860,2010.
[29]. Efstathios Stamatatos and Kostas Stergiou. Learning How to Propagate Using Random Probing [C]. InProceedings of CPAIOR–2009, Pittsburgh, PA, USA, pages263–278,2009.
[30]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. Special issue on Autonomous Search [J/OL].Constraint Programming Letters4(2008), URL http://www.constraint-programming-letters.org/(2008)
[31]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. What is autonomous search?[M]. In Panos M.Pardalos, Pascal van Hentenryck, and Michela Milano, editors, Hybrid Optimization, volume45ofOptimization and Its Applications, pages357–391. Springer, New York,2011.
[32]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. Autonomous Search [M]. Amsterdam,Netherland: Springer,2012.
[33]. Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, et al. ParamILS: An Automatic AlgorithmConfiguration Framework [J]. Journal of Artificial Intelligence Research,36(2009):267–306.
[34]. S.A. ILOG. Ilog solver6.1user’s manual [EB/OL]. Available athttp://www.cs.cornell.edu/w8/iisi/ilog/cp11/pdf/usrsolver.pdf,2005.
[35]. C. Schulte, M. Lagerkvist and G. Tack. Gecode solver [EB/OL]. Available at http://www.gecode.org,2011.
[36]. F. Laburthe and N. Jussien. Choco constraint programming system [EB/OL]. Available athttp://choco.sourceforge.net,2003–2011.
[37]. I. E. Sutherland. SKETCHPAD: A man-machine graphical communications system [R]. TechnicalReport296, MIT, Lincoln Laboratory, Jan.1963.
[38]. V. Kumar. Algorithms for constraint satisfaction problems: A survey [J]. AI Magazine,1992,13(1):32–44.
[39]. Roman Barták. On-Line Guide to Constraint Programming [EB/OL]. Available athttp://ktiml.mff.cuni.cz/~bartak/constraints/,1998.
[40]. James R. Bitner and Edward M. Reingold. Backtrack programming techniques [J]. Communicationsof the ACM,1975,18(11):651–656.
[41]. Jay P. Fillmore and S. G. Williamson. On backtracking: A combinatorial description of the algorithm[J]. SIAM Journal on Computing,1974,3(1):41–55.
[42].陈尚伟.基于Java的约束求解器的设计与实现[D].长春：吉林大学硕士士论文,2005.
[43].张居阳.基于约束的现代调度系统研究[D].长春：吉林大学博士学位论文,2006.
[44]. N. Jussien, O. Lhomme. Local search with constraint propagation and conflict-based heuristics [J].Artificial Intelligence,2002,139:21–45.
[45]. Freuder E. C., Dechter R., Ginsberg M. L., Selman B.,T sang E. P. K.. Systematic versus stochasticconstraint satisfaction [C]. In Proceedings of IJCAI–1995, Montréal, Québec, Canada, pages2027–2032,1995.
[46]. William D.Harvey. Nonsystematic backtracking search [D]. PhD thesis, California, StanfordUniversity,1995.
[47].张健.逻辑公式的可满足性判定-方法、工具及应用[M].北京：科学出版社,2000.
[48]. William D. Harvey, Matthew L. Ginsberg. Limited discrepancy search [C]. In Proceedings of theInternational Joint Conference on Artificial Intelligence, Eugene, Oregon, pages607–615,1995.
[49]. Intelligent Systems Laboratory [EB/OL]. Available at http://sicstus.sics.se/index.html,2001–2013.
[50]. Christian Schulte, Peter J. Stuckey. Efficient Constraint Propagation Engines [J]. ACM Transactionson Programming Languages and Systems,2008,31(1): Article2,1–43.
[51]. Thanasis Balafoutis, Anastasia Paparrizou, and Kostas Stergiou. Experimental Evaluation ofBranching Schemes for the CSP [EB/OL]. In: CoRR, Vol. abs/1009.0407,2010.
[52].礼欣.基于约束的调度系统的设计与实现[D].长春：吉林大学硕士士论文,2004.
[53]. M. Davis and H. Putnam. A computing procedure for quantification theory [J]. Journal of the ACM,1960,7:201–215.
[54]. Alan K. Mackworth. Consistency in networks of relations [J]. Artificial Intelligence,1977,8(1):99–118.
[55]. Farmer J D, Packard N H, Perelson A S. The Immune System [J]. Adaptation and Machine Leaning.Physica D,1986,22:187–204.
[56]. R. Dechter. Bucket elimination: A unifying framework for reasoning [J]. Artificial Intelligence,113(1999):41–85.
[57]. R. Dechter, J. Pearl. Tree clustering for constraint networks [J]. Artificial Intelligence,38(1989):353–366.
[58]. David Waltz. Understanding Line Drawings of Scenes with Shadows. In P. H. Winston, editor,ThePsychology of Computer Vision [M]. McGraw-Hill, pages19–91,1975.
[59]. Roger Mohr and Thomas C. Henderson. Arc and Path Consistency Revisited [J]. Artificial Intelligence,28(1986):225–233.
[60]. A. Mackworth. On reading sketch maps [C]. In Proceedings of IJCAI–1977, Cambridge, USA, pages598–606,1977.
[61]. Christian Bessière. Arc consistency and arc consistency again [J]. Artificial Intelligence,1994,65:179–190.
[62]. Christian Bessière, E. C. Freuder, and Jean Charles Régin. Using constraint metaknowledge to reducearc consistency computation [J]. Artificial Intelligence,1999,107:125–148.
[63]. Christian Bessière and Jean Charles Régin. Refining the basic constraint propagation algorithm [C].In Proceedings of IJCAI–2001, Seattle, WA, USA, pages309–315,2001.
[64]. Christian Bessière, Jean Charles Régin, Roland H. C.Yap and Yuanlin Zhang. An optimalcoarse-grained Arc Consistency algorithm [J]. Artificial Intelligence,2005,165(2):165–185.
[65]. Deepak Mehta and M.R.C van Dongen. Reducing checks and revisions in coarse-grained MACalgorithms [C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages236–241,2005.
[66]. Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency [C]. In Proceedingsof IJCAI–2007, Hyderabad, India, pages125–130,2007.
[67].朱兴军.约束求解的推理技术研究[D].长春：吉林大学硕士学位论文,2009.
[68]. Debruyne R and Bessière C. Some practical filtering techniques for the constraint satisfaction problem[C]. In Proceedings of IJCAI–1997, Japan, Morgan Kaufmann, pages412–417,1997.
[69]. Roman Barták and Radek Erben. A new algorithm for singleton arc consistency [C]. In Proceedings ofFLAIRS Conference,2004, Miami Beach, Florida, USA, pages257–262,2004.
[70]. Bessière C, Debruyne R. Optimal and suboptimal singleton arc consistency algorithms [C]. InProceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages54–59,2005.
[71]. Christophe Lecoutre and Stéphane Cardon. A greedy approach to establish singleton arc consistency[C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages199–204,2005.
[72]. M.R.C. Van Dongen. Beyond Singleton Arc Consistency [C]. In Proceedings of ECAI-2006, Trentino,Italy, pages163–167,2006.
[73]. Bessière, C, Debruyne, R. Theoretical analysis of singleton arc consistency and its extensions [J].Artificial Intelligence,2008,172(1):29–41.
[74]. U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing[J]. Information Science,1974,7:95–132.
[75]. C.C. Han and C.H. Lee. Comments on mohr and Henderson’s path consistency algorithm [J]. ArtificialIntelligence,1988,36:125–130.
[76]. Moninder Singh. Path consistency revisited [C].In Proceedings of the Seventh InternationalConference on Tools with Artificial Intelligence, Herndon, VA, pages318–325,1995.
[77]. Assef Chmeiss and Philippe Jégou. Sur la consistance de chemin et ses formes partielles [C]. InProceedings RFIA’96, Rennes, France, pages212–219,1996.(in French).
[78]. Assef Chmeiss and Philippe Jégou. Path-consistency: when space misses time [C]. In Proceedings ofAAAI–96, Portland, Oregon, pages196–201,1996.
[79]. Assef Chmeiss and Philippe Jégou. Efficient path-consistency propagation [J]. International Journal onArtificial Intelligence Tools,1998,7(2):121–142.
[80]. Y. Zhang and R.H.C. Yap. Making AC-3an optimal algorithm [C]. In Proceedings of IJCAI–2001,Seattle, WA, pages316–321,2001.
[81]. R. Debruyne and C. Bessi`ere. Domain Filtering Consistencies [J]. Journal of Artificial IntelligenceResearch,2001,14:205–230.
[82]. C. Bessiere, K. Stergiou, and T. Walsh. Domain filtering consistencies for non-binary constraints [J].Artificial Intelligence,2008,172(6–7):800–822.
[83]. R. Debruyne and C. Bessi`ere. From restricted path consistency to max-restricted path consistency[C].In Proceedings of CP–97, Schloss Hagenberg, Austria, pages312–326,1997.
[84]. Fabrizio Grandoni, Giuseppe F. Italiano. Improved Algorithms for Max-Restricted Path Consistency[C]. In Proceedings of CP–2003, Kinsale, Ireland, pages858–862,2003.
[85]. J. Vion, R. Debruyne. Light Algorithms for Maintaining Max-RPC During Search [C]. InProceedings of SARA2009, Lake Arrowhead, CA, pages167–174,2009.
[86]. Balafoutis T, Paparrizou A, Stergiou K, Walsh T. Improving the Performance of maxRPC [C]. InProceedings of CP–2010, St Andrews, Scotland, pages69–83,2010.
[87]. O. Roussel and C. Lecoutre. Xml representation of constraint networks: Format xcsp2.1[EB/OL]. InCoRR abs/0902.2362,2009.
[88]. D. Long and M. Fox. The third international planning competition [EB/OL]. Available athttp://www.cs.cmu.edu/afs/cs/project/jair/pub/volume20/long03ahtml/node37.html,2002.
[89]. ROADEF’2001: FAPP [EB/OL]. Available at http://uma.ensta.fr/conf/roadef-2001-challenge/.
[90]. B. Cabon, S. De Givry, L. Lobjois, T. Schiex, and J.P. Warners. Radio Link Frequency Assignment [J].Constraints,1999,4(1):79–89.
[91]. Christian Bessière, Assef Chmeiss and Lakhdar Sa s. Neighborhood-based variable ordering heuristicsfor the constraint satisfaction problem [C]. In Proceedings of CP-2001, LNCS2239, Paphos, Cyprus,pages565–569,2001.
[92]. Carla P. Gomes, David Shmoys. Completing quasi-groups or latin squares: a structured graph coloringproblem [C]. In Proceedings of Computational Symposium on Graph Coloring and Generalizations,2002.
[93]. Philippe Laborie. Complete MCS-based search: Application to resource constrained project scheduling[C]. In Proceedings of IJCAI–2005,Edinburgh, Scotland, pages181–186,2005.
[94]. W. P. M. Nuijten, E. H. L. Aarts. A computational study of constraint satisfaction for multiplecapacitated job shop scheduling [J]. European Journal of Operational Research,1996,90(2):269–284.
[95]. Christophe Lecoutre, Frédéric Boussemart, Fred Hemery. Backjump-based techniques versusconflict-directed heuristics [C]. In Proceedings of the16thIEEE International Conference on Toolswith Artificial Intelligence, Boca Raton, Florida, USA, pages549–557,2004.
[96]. F. Bacchus. Extending forward checking [C]. In Proceedings of CP-2000, Singapore, pages35–51,2000.
[97]. B.M.Smith and M.E.Dyer. Locating the phase transition in binary constraint satisfaction problems [J].Artificial Intelligence,1996,81(1–2):155–181.
[98]. I.P.Gent, E.MacIntyre, P.Prosser, B.M.Smith, and T. Walsh. Random constraint satisfaction: flaws andstructure [J]. Constraints,2001,6(4):345–372.
[99]. Ke Xu and Wei Li. Many Hard Examples in Exact Phase Transitions with application to generatinghard satisfiable instances [R].CoRR Report cs. CC/0302001,2003.
[100]. Ke Xu, Frédéric Boussemart, Fred Hemery, Christophe Lecoutre. A simple model to generate hardsatisfiable instances [C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, pages337–342,2005.
[101]. Robert M. Haralick and Gordon L. Elliott. Increasing tree search efficiency for constraint satisfactionproblems [J]. Artificial Intelligence,1980,14(3):263–313.
[102]. G. Kondrak and P. van Beek. A theoretical evaluation of selected backtracking algorithms [J].Artificial Intelligence,1997,89:365–387.
[103]. G. Smolka. The OZ Programming Model [C]. In Computer Science Today (LNCS1000), pages324–343,1995.
[104]. Vincent Park. An empirical study of different branching strategies [D]. Ontario, Canada: University ofWaterloo,2004.
[105]. M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The ConstraintLogic Programming Language CHIP [C]. In Proceedings of FGCS–88, Tokyo, Japan, pages693–702,1988.
[106]. Hutter F, Hoos HH, Leyton-Brown K, Stützle T. ParamILS:an Automatic Algorithm ConfigurationFramework [J]. Journal of Artificial Intelligence Research,2009,36:267–306.
[107]. Hamadi Y, Monfroy E, Saubion F. Autonomous Search [M]. Berlin: Springer,2012
[108]. Barbara M. Smith and Stuart A. Grant. Trying Harder to Fail First [C]. In Proceedings of ECAI–1998,Brighton, UK, pages249–253,1998.
[109]. Likitvivatanavong C, Zhang YL, Bowen J, Shannon S, Freuder EC. Arc Consistency During Search[C]. In Proceedings of IJCAI–2007, Hyderabad, India, pages137–142,2007.
[110].孙吉贵,高健,张永刚.一个基于最小冲突修补的动态约束满足求解算法[J].计算机研究与发展,2007,44(12):2078–2084.
[111]. Daniel Frost, Rina Dechter. Look-Ahead Value Ordering for Constraint Satisfaction Problems [C]. InProceedings of IJCAI–1995, Montréal, Québec, Canada, pages572–578,1995.
[112]. Daniel Frost and Rina Dechter. In search of the best constraint satisfaction search [C]. In Proceedingsof the Twelfth National Conference on Artificial Intelligence, Seattle, Washington, pages301–306,1994.
[113]. Carla P. Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-Tailed Phenomena inSatisfiability and Constraint Satisfaction Problems [J]. Journal of Automated Reasoning,2000,24:67–100.
[114]. Rina Dechter and Itay Meiri. Experimental Evaluation of Preprocessing Techniques in ConstraintSatisfaction Problems [C]. In Proceedings of IJCAI–1989, Detroit, Michigan, USA, pages271–277,1989.
[115]. Eugene C. Freuder. A Sufficient Condition for Backtrack-Free Search [J]. Journal of the ACM,1982,29(1):24–32.
[116]. Christian Bessiere and Jean-Charles Regin. MAC and Combined Heuristics: Two Reasons to ForsakeFC (and CBJ?) on Hard Problems [C]. In Proceedings of CP–1996, Cambridge, Massachusetts, pages61–75,1996.
[117]. Daniel Brélaz. New Methods to Color the Vertices of a Graph [J].Communications of the ACM,1979,22:251–256.
[118]. Barbara M. Smith. The Brélaz Heuristic and Optimal Static Orderings [C]. In Proceedings ofCP–1999, Alexandria, Virginia, pages405–418,1999.
[119]. M. Correia and P. Barahona. On the integration of singleton consistency and look-ahead heuristics [C].In Proceedings of the ERCIM workshop–CSCLP, Yvelines, France, pages47–60,2007.
[120]. H. Cambazard and N. Jussien. Identifying and Exploiting Problem Structures UsingExplanation-based Constraint Programming [J]. Constraints,2006,11:295–313.
[121]. P. Refalo. Impact-based search strategies for constraint programming [C]. In Proceedings of CP-2004,Toronto, Canada, pages556–571,2004.
[122]. R.J.Wallace and D. Grimes. Experimental studies of variable selection strategies based on constraintweights [J]. Journal of Algorithms,2008,63(1–3):114–129.
[123]. R. Wallace and E. Freuder. Ordering heuristics for arc consistency algorithms [C]. In Proceedings ofAI/GI/VI, Vancouver, British Columbia, Canada, pages163–169,1992.
[124]. F. Boussemart, F. Hemery, and C. Lecoutre. Revision ordering heuristics for the ConstraintSatisfaction Problem [C]. In proceedings of CP–2004, Workshop on Constraint Propagation andImplementation, Toronto, Canada, pages29–43,2004.
[125]. Dechter, R. and Pearl, J. Network-based Heuristics for Constraint Satisfaction Problems [J]. ArtificialIntelligence,1988,34:1–38.
[126]. Amnon Meisels, Solomon Eyal Shimony, and Gadi Solotorevsky. Bayes Networks for Estimating theNumber of Solutions to a CSP [C]. In Proceedings of AAAI–1997, Providence, Rhode Island, pages185–190,1997.
[127]. Matt Vernooy and William S. Harvens. An Examination of Probabilistic Value-Ordering Heuristics[C]. In Proceedings of the Australian Joint Conference on Artificial Intelligence, Sydney, Australia,pages340–352,1999.
[128]. K. Kask, R. Dechter and V. Gogate. Counting-Based Look-Ahead Schemes for ConstraintSatisfaction [C]. In Proceedings of CP–2004, Toronto, Canada, pages317–331,2004.
[129]. P. A. Geelen. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems [C]. InProceedings of ECAI–1992, Vienna, Austria, pages31–35,1992.
[130]. Matthew L. Ginsberg, Michael Frank, Michael P. Halpin and Mark C. Torrance. Search LessonsLearned from Crossword Puzzles [C]. In Proceedings of AAAI–1990, Boston, Massachusetts, pages210215,1990.
[131]. Alessandro Zanarini and Gilles Pesant. Solution Counting Algorithms for Constraint-Centered SearchHeuristics [C]. In Proceedings of CP–2007, Providence, RI, USA, pages743–757,2007.
[132]. Deepak Mehta and M.R.C. von Dongen. Static Value Ordering Heuristics for Constraint SatisfactionProblems [C]. In Proceedings of CPAI–2005, Sitges, Spain, pages6578,2005.
[133]. Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary and Vincent Vidal. Nogood Recording fromRestarts [C]. In Proceedings of IJCAI–2007, Hyderabad, India, pages131–136,2007.
[134]. J. Christopher Beck. Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling [J].Journal of Artificial Intelligence Research,29:49–77,2007.
[135]. Susan L. Epstein, Eugene C. Freuder, and Richard J. Wallace. Learning to Support ConstraintProgrammers [J].Computational Intelligence,2005,21:337–371.
[136]. Steven Minton. Automatically Configuring Constraint Satisfaction Programs: A Case Study [J].Constraints,1996,1:7–44.
[137]. Zhijun Zhang and Susan L. Epstein. Learned Value-Ordering Heuristics for Constraint Satisfaction[C]. In Proceedings of AAAI–2008, Chicago, Illinois, USA, pages154–161,2008.
[138]. Carla P. Gomes, Cèsar Fernández, Bart Selman, and Christian Bessière. Statistical Regimes AcrossConstrainedness Regions [C]. In Proceedings of CP–2004, Toronto, Canada, pages3246,2004.
[139]. D. A. Huffman. Impossible objects as nonsense sentences [M]. In B. Meltzer and D. Michie, editors,Machine Intelligence6, pages295–323. Edinburgh Univ. Press,1971.
[140]. M. B. Clowes. On seeing things [J]. Artificial Intelligence,1971,2:79–116.
[141]. A. K. Mackworth. Interpreting pictures of polyhedral scenes [J]. Artificial Intelligence,1973,4:121–137.
[142]. E. C. Freuder. Synthesizing constraint expressions [J]. Comm. ACM,1978,21:958–966.
[143].王海燕，郭劲松，欧阳丹彤，张永刚.基于比特位操作的自适应约束传播算法[J].吉林大学学报（工学版）,2012,42(5):1219–1224.
[144]. Christophe Lecoutre and Julien Vion. Enforcing Arc Consistency using Bitwise Operations [J].Constraint Programming Letters,2008,2:21–35.
[145]. Jinsong Guo and Zhanshan Li. MaxRPC Algorithms Based on Bitwise Operations [C]. In Proceedingsof CP–2011, Perugia, Italy, pages373–384,2011.
[146]. Christian Bessière, Stéphane Cardon, Romuald Debruyne, et al. Efficient Algorithms for SingletonArc Consistency [J]. Constraints,2011,16(1):25–53.
[147]. J.C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms [M]. Kluwer AcademicPublishers, Norwell,1981.
[2]. Francois Rossi, Peter van Beek, and Toby Walsh, editors. Handbook of Constraint Programming [M].Amsterdam, Netherland: Elsevier,2006.
[3]. Alan K.Mackworth and Eugene C.Freuder. The Complexity of some polynomial network consistencyalgorithms for constraint satisfaction problems [J]. Artificial Intelligence,1985,25:65–74.
[4]. Tsang Edward. Foundations of Constraint Satisfaction [M]. London:Academic Press,1993.
[5].刘春晖.基于约束传播的约束求解方法研究[D].长春：吉林大学博士论文,2008.
[6].王秦辉,陈恩红,王煦法.分布式约束满足问题研究及其进展[J].软件学报,2006,17(10):2029–2039.
[7].季晓慧,黄拙,张健.约束求解与优化技术的结合[J].计算机学报,2005,28(11):1790–1797.
[8]. Runming Lu, Sheng Liu and Jian Zhang. Searching for Doubly Self-Orthogonal Latin Squares [C]. InProceedings of cp–2011, Perugia, Italy, pages538–545,2011.
[9]. Ke Xu and Wei Li. Exact Phase Transitions in Random Constraint Satisfaction Problems [J]. Journalof Artificial Intelligence Research,12(2000):93–103.
[10]. Ke Xu and Wei Li. Many Hard Examples in Exact Phase Transitions [J]. Theoretical ComputerScience,355(2006):291–302.
[11]. Ke Xu, Frederic Boussemart, Fred Hemery and ChristopheLecoutre. Random Constraint Satisfaction:Easy Generation of Hard (Satisfiable) Instances [J]. Artificial Intelligence,2007,171(8–9):514–534.
[12].高健.基于推理的约束满足问题求解算法研究[D].长春：吉林大学硕士士论文,2008.
[13]. D. Cohen, P. Jeavons, P. Jonsson, and M. Koubarakis. Building tractable disjunctive constraints [J].Journal of the ACM,47(2000):826–853.
[14]. Rina Dechter. Constraint processing [M]. San Francisco: Morgan Kaufmann Publishers,2003.
[15]. Patrick Prosser. Hybrid algorithms for the constraint satisfaction problems [J]. ComputationalIntelligence,1993,9(3):268–299.
[16]. Matthew L. Ginsberg. Dynamic backtracking [J]. Artificial Intelligence,1993,(1):25–46.
[17]. Thanasis Balafoutis. Adaptive strategies for solving CSP [D]. Aegean, Greece: University of theAegean,2011.
[18]. J.E. Borrett, E.P.K. Tsang and N.R. Walsh. Adaptive constraint satisfaction [C]. In Proceedings of15thUK Planning and Scheduling Special Interest Group Workshop, Liverpool, UK,1996.
[19]. James E. Borrett and Edward P.K. Tsang. Adaptive constraint satisfaction: the quickest first principle[J]. Computational Intelligence: Collaboration, Fusion and Emergence, Intelligent Systems ReferenceLibrary,1(2009),203–230.
[20]. Susan L. Epstein, Eugene C. Freuder, Richard Wallace, Anton Morozov and Bruce Samuels. Theadaptive constraint engine [C]. In Proceedings of CP–2002, New York, USA, pages525–540,2002.
[21]. Frédéric Boussemart, Fred Heremy, Christophe Lecoutre, and Lakhdar Sais. Boosting SystematicSearch by Weighting Constraints [C]. In Proceedings of ECAI–2004, Valencia, Spain, pages482–486,2004.
[22]. Diarmuid Grimes and Richard J. Wallace. Sampling Strategies and Variable Selection in WeightedDegree Heuristics [C]. In Proceedings of CP–2007, Providence, USA, pages831–838,2007.
[23]. Deepak Mehta and M.R.C. van Dongen. Probabilistic Consistency Boosts MAC and SAC [C]. InProceedings of IJCAI–2007, Hyderabad, India, pages143–148,2007.
[24]. El Sakkout, Mark Wallace, and Barry Richards. An Instance of Adaptive Constraint Propagation [C].In Proceedings of CP–96, Cambridge MA, pages164–178,1996.
[25]. Eugene C. Freuder and Richard J. Wallace. Selective Relaxation for Constraint Satisfaction Problems[C]. In Proceedings of the Third International IEEE Computer Society Conference on Tools forArtificial Intelligence, San Jose, USA, pages332–339,1991.
[26]. Christian Schulte and Peter Stuckey. Speeding Up Constraint Propagation [C]. In Proceedings ofCP–2004, Toronto, Canada, pages619–633,2004.
[27]. Kostas Stergiou. Heuristics for Dynamically Adapting Propagation [C]. In Proceedings of ECAI–2008,Patras, Greece, pages485–489,2008.
[28]. Thanasis Balafoutis and Kostas Stergiou. Adaptive Branching for Constraint Satisfaction Problems[C]. In Proceedings of ECAI–2010, Lisbon, Portugal, pages855–860,2010.
[29]. Efstathios Stamatatos and Kostas Stergiou. Learning How to Propagate Using Random Probing [C]. InProceedings of CPAIOR–2009, Pittsburgh, PA, USA, pages263–278,2009.
[30]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. Special issue on Autonomous Search [J/OL].Constraint Programming Letters4(2008), URL http://www.constraint-programming-letters.org/(2008)
[31]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. What is autonomous search?[M]. In Panos M.Pardalos, Pascal van Hentenryck, and Michela Milano, editors, Hybrid Optimization, volume45ofOptimization and Its Applications, pages357–391. Springer, New York,2011.
[32]. Youssef Hamadi, Eric Monfroy and Frédéric Saubion. Autonomous Search [M]. Amsterdam,Netherland: Springer,2012.
[33]. Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, et al. ParamILS: An Automatic AlgorithmConfiguration Framework [J]. Journal of Artificial Intelligence Research,36(2009):267–306.
[34]. S.A. ILOG. Ilog solver6.1user’s manual [EB/OL]. Available athttp://www.cs.cornell.edu/w8/iisi/ilog/cp11/pdf/usrsolver.pdf,2005.
[35]. C. Schulte, M. Lagerkvist and G. Tack. Gecode solver [EB/OL]. Available at http://www.gecode.org,2011.
[36]. F. Laburthe and N. Jussien. Choco constraint programming system [EB/OL]. Available athttp://choco.sourceforge.net,2003–2011.
[37]. I. E. Sutherland. SKETCHPAD: A man-machine graphical communications system [R]. TechnicalReport296, MIT, Lincoln Laboratory, Jan.1963.
[38]. V. Kumar. Algorithms for constraint satisfaction problems: A survey [J]. AI Magazine,1992,13(1):32–44.
[39]. Roman Barták. On-Line Guide to Constraint Programming [EB/OL]. Available athttp://ktiml.mff.cuni.cz/~bartak/constraints/,1998.
[40]. James R. Bitner and Edward M. Reingold. Backtrack programming techniques [J]. Communicationsof the ACM,1975,18(11):651–656.
[41]. Jay P. Fillmore and S. G. Williamson. On backtracking: A combinatorial description of the algorithm[J]. SIAM Journal on Computing,1974,3(1):41–55.
[42].陈尚伟.基于Java的约束求解器的设计与实现[D].长春：吉林大学硕士士论文,2005.
[43].张居阳.基于约束的现代调度系统研究[D].长春：吉林大学博士学位论文,2006.
[44]. N. Jussien, O. Lhomme. Local search with constraint propagation and conflict-based heuristics [J].Artificial Intelligence,2002,139:21–45.
[45]. Freuder E. C., Dechter R., Ginsberg M. L., Selman B.,T sang E. P. K.. Systematic versus stochasticconstraint satisfaction [C]. In Proceedings of IJCAI–1995, Montréal, Québec, Canada, pages2027–2032,1995.
[46]. William D.Harvey. Nonsystematic backtracking search [D]. PhD thesis, California, StanfordUniversity,1995.
[47].张健.逻辑公式的可满足性判定-方法、工具及应用[M].北京：科学出版社,2000.
[48]. William D. Harvey, Matthew L. Ginsberg. Limited discrepancy search [C]. In Proceedings of theInternational Joint Conference on Artificial Intelligence, Eugene, Oregon, pages607–615,1995.
[49]. Intelligent Systems Laboratory [EB/OL]. Available at http://sicstus.sics.se/index.html,2001–2013.
[50]. Christian Schulte, Peter J. Stuckey. Efficient Constraint Propagation Engines [J]. ACM Transactionson Programming Languages and Systems,2008,31(1): Article2,1–43.
[51]. Thanasis Balafoutis, Anastasia Paparrizou, and Kostas Stergiou. Experimental Evaluation ofBranching Schemes for the CSP [EB/OL]. In: CoRR, Vol. abs/1009.0407,2010.
[52].礼欣.基于约束的调度系统的设计与实现[D].长春：吉林大学硕士士论文,2004.
[53]. M. Davis and H. Putnam. A computing procedure for quantification theory [J]. Journal of the ACM,1960,7:201–215.
[54]. Alan K. Mackworth. Consistency in networks of relations [J]. Artificial Intelligence,1977,8(1):99–118.
[55]. Farmer J D, Packard N H, Perelson A S. The Immune System [J]. Adaptation and Machine Leaning.Physica D,1986,22:187–204.
[56]. R. Dechter. Bucket elimination: A unifying framework for reasoning [J]. Artificial Intelligence,113(1999):41–85.
[57]. R. Dechter, J. Pearl. Tree clustering for constraint networks [J]. Artificial Intelligence,38(1989):353–366.
[58]. David Waltz. Understanding Line Drawings of Scenes with Shadows. In P. H. Winston, editor,ThePsychology of Computer Vision [M]. McGraw-Hill, pages19–91,1975.
[59]. Roger Mohr and Thomas C. Henderson. Arc and Path Consistency Revisited [J]. Artificial Intelligence,28(1986):225–233.
[60]. A. Mackworth. On reading sketch maps [C]. In Proceedings of IJCAI–1977, Cambridge, USA, pages598–606,1977.
[61]. Christian Bessière. Arc consistency and arc consistency again [J]. Artificial Intelligence,1994,65:179–190.
[62]. Christian Bessière, E. C. Freuder, and Jean Charles Régin. Using constraint metaknowledge to reducearc consistency computation [J]. Artificial Intelligence,1999,107:125–148.
[63]. Christian Bessière and Jean Charles Régin. Refining the basic constraint propagation algorithm [C].In Proceedings of IJCAI–2001, Seattle, WA, USA, pages309–315,2001.
[64]. Christian Bessière, Jean Charles Régin, Roland H. C.Yap and Yuanlin Zhang. An optimalcoarse-grained Arc Consistency algorithm [J]. Artificial Intelligence,2005,165(2):165–185.
[65]. Deepak Mehta and M.R.C van Dongen. Reducing checks and revisions in coarse-grained MACalgorithms [C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages236–241,2005.
[66]. Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency [C]. In Proceedingsof IJCAI–2007, Hyderabad, India, pages125–130,2007.
[67].朱兴军.约束求解的推理技术研究[D].长春：吉林大学硕士学位论文,2009.
[68]. Debruyne R and Bessière C. Some practical filtering techniques for the constraint satisfaction problem[C]. In Proceedings of IJCAI–1997, Japan, Morgan Kaufmann, pages412–417,1997.
[69]. Roman Barták and Radek Erben. A new algorithm for singleton arc consistency [C]. In Proceedings ofFLAIRS Conference,2004, Miami Beach, Florida, USA, pages257–262,2004.
[70]. Bessière C, Debruyne R. Optimal and suboptimal singleton arc consistency algorithms [C]. InProceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages54–59,2005.
[71]. Christophe Lecoutre and Stéphane Cardon. A greedy approach to establish singleton arc consistency[C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, UK, pages199–204,2005.
[72]. M.R.C. Van Dongen. Beyond Singleton Arc Consistency [C]. In Proceedings of ECAI-2006, Trentino,Italy, pages163–167,2006.
[73]. Bessière, C, Debruyne, R. Theoretical analysis of singleton arc consistency and its extensions [J].Artificial Intelligence,2008,172(1):29–41.
[74]. U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing[J]. Information Science,1974,7:95–132.
[75]. C.C. Han and C.H. Lee. Comments on mohr and Henderson’s path consistency algorithm [J]. ArtificialIntelligence,1988,36:125–130.
[76]. Moninder Singh. Path consistency revisited [C].In Proceedings of the Seventh InternationalConference on Tools with Artificial Intelligence, Herndon, VA, pages318–325,1995.
[77]. Assef Chmeiss and Philippe Jégou. Sur la consistance de chemin et ses formes partielles [C]. InProceedings RFIA’96, Rennes, France, pages212–219,1996.(in French).
[78]. Assef Chmeiss and Philippe Jégou. Path-consistency: when space misses time [C]. In Proceedings ofAAAI–96, Portland, Oregon, pages196–201,1996.
[79]. Assef Chmeiss and Philippe Jégou. Efficient path-consistency propagation [J]. International Journal onArtificial Intelligence Tools,1998,7(2):121–142.
[80]. Y. Zhang and R.H.C. Yap. Making AC-3an optimal algorithm [C]. In Proceedings of IJCAI–2001,Seattle, WA, pages316–321,2001.
[81]. R. Debruyne and C. Bessi`ere. Domain Filtering Consistencies [J]. Journal of Artificial IntelligenceResearch,2001,14:205–230.
[82]. C. Bessiere, K. Stergiou, and T. Walsh. Domain filtering consistencies for non-binary constraints [J].Artificial Intelligence,2008,172(6–7):800–822.
[83]. R. Debruyne and C. Bessi`ere. From restricted path consistency to max-restricted path consistency[C].In Proceedings of CP–97, Schloss Hagenberg, Austria, pages312–326,1997.
[84]. Fabrizio Grandoni, Giuseppe F. Italiano. Improved Algorithms for Max-Restricted Path Consistency[C]. In Proceedings of CP–2003, Kinsale, Ireland, pages858–862,2003.
[85]. J. Vion, R. Debruyne. Light Algorithms for Maintaining Max-RPC During Search [C]. InProceedings of SARA2009, Lake Arrowhead, CA, pages167–174,2009.
[86]. Balafoutis T, Paparrizou A, Stergiou K, Walsh T. Improving the Performance of maxRPC [C]. InProceedings of CP–2010, St Andrews, Scotland, pages69–83,2010.
[87]. O. Roussel and C. Lecoutre. Xml representation of constraint networks: Format xcsp2.1[EB/OL]. InCoRR abs/0902.2362,2009.
[88]. D. Long and M. Fox. The third international planning competition [EB/OL]. Available athttp://www.cs.cmu.edu/afs/cs/project/jair/pub/volume20/long03ahtml/node37.html,2002.
[89]. ROADEF’2001: FAPP [EB/OL]. Available at http://uma.ensta.fr/conf/roadef-2001-challenge/.
[90]. B. Cabon, S. De Givry, L. Lobjois, T. Schiex, and J.P. Warners. Radio Link Frequency Assignment [J].Constraints,1999,4(1):79–89.
[91]. Christian Bessière, Assef Chmeiss and Lakhdar Sa s. Neighborhood-based variable ordering heuristicsfor the constraint satisfaction problem [C]. In Proceedings of CP-2001, LNCS2239, Paphos, Cyprus,pages565–569,2001.
[92]. Carla P. Gomes, David Shmoys. Completing quasi-groups or latin squares: a structured graph coloringproblem [C]. In Proceedings of Computational Symposium on Graph Coloring and Generalizations,2002.
[93]. Philippe Laborie. Complete MCS-based search: Application to resource constrained project scheduling[C]. In Proceedings of IJCAI–2005,Edinburgh, Scotland, pages181–186,2005.
[94]. W. P. M. Nuijten, E. H. L. Aarts. A computational study of constraint satisfaction for multiplecapacitated job shop scheduling [J]. European Journal of Operational Research,1996,90(2):269–284.
[95]. Christophe Lecoutre, Frédéric Boussemart, Fred Hemery. Backjump-based techniques versusconflict-directed heuristics [C]. In Proceedings of the16thIEEE International Conference on Toolswith Artificial Intelligence, Boca Raton, Florida, USA, pages549–557,2004.
[96]. F. Bacchus. Extending forward checking [C]. In Proceedings of CP-2000, Singapore, pages35–51,2000.
[97]. B.M.Smith and M.E.Dyer. Locating the phase transition in binary constraint satisfaction problems [J].Artificial Intelligence,1996,81(1–2):155–181.
[98]. I.P.Gent, E.MacIntyre, P.Prosser, B.M.Smith, and T. Walsh. Random constraint satisfaction: flaws andstructure [J]. Constraints,2001,6(4):345–372.
[99]. Ke Xu and Wei Li. Many Hard Examples in Exact Phase Transitions with application to generatinghard satisfiable instances [R].CoRR Report cs. CC/0302001,2003.
[100]. Ke Xu, Frédéric Boussemart, Fred Hemery, Christophe Lecoutre. A simple model to generate hardsatisfiable instances [C]. In Proceedings of IJCAI–2005, Edinburgh, Scotland, pages337–342,2005.
[101]. Robert M. Haralick and Gordon L. Elliott. Increasing tree search efficiency for constraint satisfactionproblems [J]. Artificial Intelligence,1980,14(3):263–313.
[102]. G. Kondrak and P. van Beek. A theoretical evaluation of selected backtracking algorithms [J].Artificial Intelligence,1997,89:365–387.
[103]. G. Smolka. The OZ Programming Model [C]. In Computer Science Today (LNCS1000), pages324–343,1995.
[104]. Vincent Park. An empirical study of different branching strategies [D]. Ontario, Canada: University ofWaterloo,2004.
[105]. M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, and F. Berthier. The ConstraintLogic Programming Language CHIP [C]. In Proceedings of FGCS–88, Tokyo, Japan, pages693–702,1988.
[106]. Hutter F, Hoos HH, Leyton-Brown K, Stützle T. ParamILS:an Automatic Algorithm ConfigurationFramework [J]. Journal of Artificial Intelligence Research,2009,36:267–306.
[107]. Hamadi Y, Monfroy E, Saubion F. Autonomous Search [M]. Berlin: Springer,2012
[108]. Barbara M. Smith and Stuart A. Grant. Trying Harder to Fail First [C]. In Proceedings of ECAI–1998,Brighton, UK, pages249–253,1998.
[109]. Likitvivatanavong C, Zhang YL, Bowen J, Shannon S, Freuder EC. Arc Consistency During Search[C]. In Proceedings of IJCAI–2007, Hyderabad, India, pages137–142,2007.
[110].孙吉贵,高健,张永刚.一个基于最小冲突修补的动态约束满足求解算法[J].计算机研究与发展,2007,44(12):2078–2084.
[111]. Daniel Frost, Rina Dechter. Look-Ahead Value Ordering for Constraint Satisfaction Problems [C]. InProceedings of IJCAI–1995, Montréal, Québec, Canada, pages572–578,1995.
[112]. Daniel Frost and Rina Dechter. In search of the best constraint satisfaction search [C]. In Proceedingsof the Twelfth National Conference on Artificial Intelligence, Seattle, Washington, pages301–306,1994.
[113]. Carla P. Gomes, Bart Selman, Nuno Crato, and Henry Kautz. Heavy-Tailed Phenomena inSatisfiability and Constraint Satisfaction Problems [J]. Journal of Automated Reasoning,2000,24:67–100.
[114]. Rina Dechter and Itay Meiri. Experimental Evaluation of Preprocessing Techniques in ConstraintSatisfaction Problems [C]. In Proceedings of IJCAI–1989, Detroit, Michigan, USA, pages271–277,1989.
[115]. Eugene C. Freuder. A Sufficient Condition for Backtrack-Free Search [J]. Journal of the ACM,1982,29(1):24–32.
[116]. Christian Bessiere and Jean-Charles Regin. MAC and Combined Heuristics: Two Reasons to ForsakeFC (and CBJ?) on Hard Problems [C]. In Proceedings of CP–1996, Cambridge, Massachusetts, pages61–75,1996.
[117]. Daniel Brélaz. New Methods to Color the Vertices of a Graph [J].Communications of the ACM,1979,22:251–256.
[118]. Barbara M. Smith. The Brélaz Heuristic and Optimal Static Orderings [C]. In Proceedings ofCP–1999, Alexandria, Virginia, pages405–418,1999.
[119]. M. Correia and P. Barahona. On the integration of singleton consistency and look-ahead heuristics [C].In Proceedings of the ERCIM workshop–CSCLP, Yvelines, France, pages47–60,2007.
[120]. H. Cambazard and N. Jussien. Identifying and Exploiting Problem Structures UsingExplanation-based Constraint Programming [J]. Constraints,2006,11:295–313.
[121]. P. Refalo. Impact-based search strategies for constraint programming [C]. In Proceedings of CP-2004,Toronto, Canada, pages556–571,2004.
[122]. R.J.Wallace and D. Grimes. Experimental studies of variable selection strategies based on constraintweights [J]. Journal of Algorithms,2008,63(1–3):114–129.
[123]. R. Wallace and E. Freuder. Ordering heuristics for arc consistency algorithms [C]. In Proceedings ofAI/GI/VI, Vancouver, British Columbia, Canada, pages163–169,1992.
[124]. F. Boussemart, F. Hemery, and C. Lecoutre. Revision ordering heuristics for the ConstraintSatisfaction Problem [C]. In proceedings of CP–2004, Workshop on Constraint Propagation andImplementation, Toronto, Canada, pages29–43,2004.
[125]. Dechter, R. and Pearl, J. Network-based Heuristics for Constraint Satisfaction Problems [J]. ArtificialIntelligence,1988,34:1–38.
[126]. Amnon Meisels, Solomon Eyal Shimony, and Gadi Solotorevsky. Bayes Networks for Estimating theNumber of Solutions to a CSP [C]. In Proceedings of AAAI–1997, Providence, Rhode Island, pages185–190,1997.
[127]. Matt Vernooy and William S. Harvens. An Examination of Probabilistic Value-Ordering Heuristics[C]. In Proceedings of the Australian Joint Conference on Artificial Intelligence, Sydney, Australia,pages340–352,1999.
[128]. K. Kask, R. Dechter and V. Gogate. Counting-Based Look-Ahead Schemes for ConstraintSatisfaction [C]. In Proceedings of CP–2004, Toronto, Canada, pages317–331,2004.
[129]. P. A. Geelen. Dual Viewpoint Heuristics for Binary Constraint Satisfaction Problems [C]. InProceedings of ECAI–1992, Vienna, Austria, pages31–35,1992.
[130]. Matthew L. Ginsberg, Michael Frank, Michael P. Halpin and Mark C. Torrance. Search LessonsLearned from Crossword Puzzles [C]. In Proceedings of AAAI–1990, Boston, Massachusetts, pages210215,1990.
[131]. Alessandro Zanarini and Gilles Pesant. Solution Counting Algorithms for Constraint-Centered SearchHeuristics [C]. In Proceedings of CP–2007, Providence, RI, USA, pages743–757,2007.
[132]. Deepak Mehta and M.R.C. von Dongen. Static Value Ordering Heuristics for Constraint SatisfactionProblems [C]. In Proceedings of CPAI–2005, Sitges, Spain, pages6578,2005.
[133]. Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary and Vincent Vidal. Nogood Recording fromRestarts [C]. In Proceedings of IJCAI–2007, Hyderabad, India, pages131–136,2007.
[134]. J. Christopher Beck. Solution-Guided Multi-Point Constructive Search for Job Shop Scheduling [J].Journal of Artificial Intelligence Research,29:49–77,2007.
[135]. Susan L. Epstein, Eugene C. Freuder, and Richard J. Wallace. Learning to Support ConstraintProgrammers [J].Computational Intelligence,2005,21:337–371.
[136]. Steven Minton. Automatically Configuring Constraint Satisfaction Programs: A Case Study [J].Constraints,1996,1:7–44.
[137]. Zhijun Zhang and Susan L. Epstein. Learned Value-Ordering Heuristics for Constraint Satisfaction[C]. In Proceedings of AAAI–2008, Chicago, Illinois, USA, pages154–161,2008.
[138]. Carla P. Gomes, Cèsar Fernández, Bart Selman, and Christian Bessière. Statistical Regimes AcrossConstrainedness Regions [C]. In Proceedings of CP–2004, Toronto, Canada, pages3246,2004.
[139]. D. A. Huffman. Impossible objects as nonsense sentences [M]. In B. Meltzer and D. Michie, editors,Machine Intelligence6, pages295–323. Edinburgh Univ. Press,1971.
[140]. M. B. Clowes. On seeing things [J]. Artificial Intelligence,1971,2:79–116.
[141]. A. K. Mackworth. Interpreting pictures of polyhedral scenes [J]. Artificial Intelligence,1973,4:121–137.
[142]. E. C. Freuder. Synthesizing constraint expressions [J]. Comm. ACM,1978,21:958–966.
[143].王海燕，郭劲松，欧阳丹彤，张永刚.基于比特位操作的自适应约束传播算法[J].吉林大学学报（工学版）,2012,42(5):1219–1224.
[144]. Christophe Lecoutre and Julien Vion. Enforcing Arc Consistency using Bitwise Operations [J].Constraint Programming Letters,2008,2:21–35.
[145]. Jinsong Guo and Zhanshan Li. MaxRPC Algorithms Based on Bitwise Operations [C]. In Proceedingsof CP–2011, Perugia, Italy, pages373–384,2011.
[146]. Christian Bessière, Stéphane Cardon, Romuald Debruyne, et al. Efficient Algorithms for SingletonArc Consistency [J]. Constraints,2011,16(1):25–53.
[147]. J.C. Bezdek. Pattern Recognition with Fuzzy Objective Function Algorithms [M]. Kluwer AcademicPublishers, Norwell,1981.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |