Branching constraint satisfaction problems and Markov decision problems compared

被引：7
作者：
Fowler, DW [1 ]
Brown, KN [1 ]
机构：
[1] Univ Aberdeen, Dept Comp Sci, Aberdeen, Scotland
来源：
ANNALS OF OPERATIONS RESEARCH | 2003年 / 118卷 / 1-4期
关键词：
constraint satisfaction; uncertainty; Markov decision problems;
D O I：
10.1023/A:1021853506616
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
Branching Constraint Satisfaction Problems (BCSPs) model a class of uncertain dynamic resource allocation problems. We describe the features of BCSPs, and show that the associated decision problem is NP-complete. Markov Decision Problems could be used in place of BCSPs, but we show analytically and empirically that, for the class of problems in question, the BCSP algorithms are more efficient than the related MDP algorithms.
引用
收藏
页码：85 / 100
页数：16
相关论文
共 50 条
  • [1] Branching Constraint Satisfaction Problems and Markov Decision Problems Compared
    David W. Fowler
    Kenneth N. Brown
    Annals of Operations Research, 2003, 118 : 85 - 100
  • [2] Branching Schemes and Variable Ordering Heuristics for Constraint Satisfaction Problems: Is There Something to Learn?
    Ortiz-Bayliss, Jose Carlos
    Terashima-Marin, Hugo
    Enrique Conant-Pablos, Santiago
    NATURE INSPIRED COOPERATIVE STRATEGIES FOR OPTIMIZATION (NICSO 2013), 2014, 512 : 329 - +
  • [3] The Complexity of Constraint Satisfaction Problems
    Bodirsky, Manuel
    32ND INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2015), 2015, 30 : 2 - 9
  • [4] Constraint satisfaction problems and neurocomputing
    Nagamatu, M
    Nakano, T
    Zhang, KR
    BRAIN-INSPIRED IT I, 2004, 1269 : 161 - 164
  • [5] Uncertainty in dynamic constraint satisfaction problems
    Climent, Laura
    Salido, Miguel A.
    Wallace, Richard J.
    Barber, Federico
    AI COMMUNICATIONS, 2016, 29 (01) : 239 - 241
  • [6] Constraint satisfaction problems: Algorithms and applications
    Brailsford, SC
    Potts, CN
    Smith, BM
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1999, 119 (03) : 557 - 581
  • [7] Parameterized complexity of constraint satisfaction problems
    Dániel Marx
    computational complexity, 2005, 14 : 153 - 183
  • [8] Stability of Solutions in Constraint Satisfaction Problems
    Climent, Laura
    Salido, Miguel A.
    Barber, Federico
    ARTIFICIAL INTELLIGENCE RESEARCH AND DEVELOPMENT, 2009, 202 : 301 - 309
  • [9] Parameterized complexity of constraint satisfaction problems
    Marx, D
    COMPUTATIONAL COMPLEXITY, 2005, 14 (02) : 153 - 183
  • [10] Nonuniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
    Creignou, Nadia
    Schnoor, Henning
    Schnoor, Ilka
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2010, 11 (04) : 1 - 32
12345