Configuration Solving and Computing Explanations Based on Equivalence Class Partition
Author:
Affiliation:

  • Article
  • | |
  • Metrics
  • |
  • Reference [19]
  • |
  • Related
  • | | |
  • Comments
    Abstract:

    Some variables in a constraint-based configuration model may not have any immediate or indirect relationship between them; therefore, these variables will never intervene with each other in a constraint propagation. According to this characteristic of configuration, this paper proposes a preprocessing approach based on equivalent class partition, which can be used in the process of building the product model, so that the original configuration problem can be effectively divided into several sub-problems, and these sub-problems can be solved independently. The two backtracking-strategies are used in testing this method. The experimental results show that this method can effectively improve searching efficiency. Moreover, the method is integrated with the QUICKXPLAIN algorithm to compute conflict explanations, and the result show that it can also improve the efficiency of the algorithm.

    Reference
    [1] Freuder EC, Mackworth AK. Constraint satisfaction: An emerging paradigm. In: Rossi F, van Beek P, Walsh T, eds. Handbook ofConstraint Programming. Amsterdam: Elservier, 2006. 1-2. [doi: 10.1016/S1574-6526(06)80006-4]
    [2] van Beek P. Backtracking search algorithms. In: Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming.Amsterdam: Elservier, 2006. 1-2. [doi: 10.1016/S1574-6526(06)80008-8]
    [3] Ginsberg ML. Dynamic backtracking. Journal of Artificial Intelligence Research, 1993,1(1):1-2.
    [4] Bessiere C. Constraint propagation. In: Rossi F, van Beek P, Walsh T, eds. Handbook of Constraint Programming. Amsterdam:Elservier, 2006. 1-2.
    [5] Mackworth AK. Consistency in networks of relations. Artificial Intelligence, 1977,8(1):1-2. [doi: 10.1016/0004-3702(77)90007-8]
    [6] Mohr R, Henderson TC. Arc and path consistency revised. Artificial Intelligence, 1986,28(2):1-2. [doi: 10.1016/0004-3702(86)90083-4]
    [7] Bessiere C, Régin JC. Refining the basic constraint propagation algorithm. In: Proc. of the IJCAI 2001. 2001. 1-2.
    [8] Sabin D, Treuder EC. Contradicting conventional wisdom in constraint satisfaction. In: Cohn AG, ed. Proc. of the 11th EuropeanConf. on Artificial Intelligence. Amsterdam: John Wiley and Sons, 1994. 1-2. [doi: 10.1007/3-540-58601-6_86]
    [9] Sun JG, Zhu XJ, Zhang YG, Li Y. An approach of solving constraint satisfaction problem based on preprocessing. Chinese Journalof Computers, 2008,31(6):1-2 (in Chinese with English abstract).
    [10] Li ZS, Wang T, Sun JG, Zhang CH. Research on principle of product configurator. Application Research of Computers, 2004,24(10):1-2 (in Chinese with English abstract).
    [11] Vempaty NR. Solving constraint satisfaction problems using finite state automata. In: Swartout WR, ed. Proc. of the AAAI. SanJose: AAAI Press, 1992. 1-2.
    [12] Subbarayan S, Jensen RM, Hadzic T, Andersen HR, Møller J, Hulgaard H. Comparing two implementations of a complete andbacktrack-free interactive configurator. In: Barták R, Junker U, Silaghi MC, Zanker M, eds. Proc. of the Workshop on CSPTechniques with Immediate Application (CP-2004). 2004. 1-2. http://itu.dk/people/sathi/papers/cspia2004.pdf
    [13] Haag A, Junker U, O’sullivan B. A survey of explanation techniques for configurators. In: Sinz C, Haag A, eds. Proc. of theWorkshop on Configuration (ECAI 2006). 2006. 1-2. http://fmv.jku.at/ecai-config-ws-2006/W16.pdf
    [14] de Kleer J. An assumption-based truth maintenance system. Artificial Intelligence,1986,28(1):1-2. [doi: 10.1016/0004-3702(86)90080-9]
    [15] Junker U. QuickXplain: Preferred explanations and relaxations for over-constrained problems. In: Ferguson G, McGuinness D, eds.Proc. of the AAAI. San Jose: AAAI Press, 2004. 1-2.
    [16] van Dongen MRC, Mehta D. Queue representation for arc consistency algorithms. In: McGinty L, Crean B, eds. Proc. of the 15thIrish Conf. on Artificial Intelligence and Cognitive Science. 2004. 1-2. http://csweb.ucc.ie/~dongen/papers/AICS/04/aics04
    [17] Wallace RJ, Freuder EC. Ordering heuristics for arc consistency algorithms. In: Mellish CS, ed. Proc. of the AI/GI/VI’92. 1992.1-2. http://4c.ucc.ie/web/upload/publications/misc/wall
    [18] Smith BM, Dyer ME. Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 1996,81:1-2. [doi: 10.1016/0004-3702(95)00052-6]
    [19] Li HB, Li ZS, Ai Y, Du HY. On research of optimization strategy for dynamic backtracking. In: Wang XZ, Yeung DS, eds. Proc.of the Int’l Conf. on Machine Learning and Cybernetics, Vol.1. New York: IEEE Computer Society, 2009. 1-2.
    Related
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

李宏博,李占山,韩文成.基于等价类划分的配置求解与解释计算.软件学报,2011,22(5):929-937

Copy
Share
Article Metrics
  • Abstract:4429
  • PDF: 5878
  • HTML: 0
  • Cited by: 0
History
  • Received:April 29,2009
  • Revised:January 05,2010
You are the first2032277Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063