Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

David W. Fowler; Kenneth N. Brown

doi:10.1023/A:1021853506616

Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

David W. Fowler
, Kenneth N. Brown

University of Aberdeen

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	85-100
Number of pages	16
Journal	Annals of Operations Research
Volume	118
Issue number	1-4
DOIs	https://doi.org/10.1023/A:1021853506616
Publication status	Published - Feb 2003
Externally published	Yes

Keywords

Constraint satisfaction
Markov decision problems
Uncertainty

Access to Document

10.1023/A:1021853506616

Cite this

@article{d1393e1c961f40e09eaab9dec74b94b3,

title = "Branching Constraint Satisfaction Problems and Markov Decision Problems Compared",

abstract = "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.",

keywords = "Constraint satisfaction, Markov decision problems, Uncertainty",

author = "Fowler, \{David W.\} and Brown, \{Kenneth N.\}",

year = "2003",

month = feb,

doi = "10.1023/A:1021853506616",

language = "English",

volume = "118",

pages = "85--100",

journal = "Annals of Operations Research",

issn = "0254-5330",

publisher = "Springer Netherlands",

number = "1-4",

}

TY - JOUR

T1 - Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

AU - Fowler, David W.

AU - Brown, Kenneth N.

PY - 2003/2

Y1 - 2003/2

N2 - 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.

AB - 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.

KW - Constraint satisfaction

KW - Markov decision problems

KW - Uncertainty

UR - https://www.scopus.com/pages/publications/0037232234

U2 - 10.1023/A:1021853506616

DO - 10.1023/A:1021853506616

M3 - Article

AN - SCOPUS:0037232234

SN - 0254-5330

VL - 118

SP - 85

EP - 100

JO - Annals of Operations Research

JF - Annals of Operations Research

IS - 1-4

ER -

Branching Constraint Satisfaction Problems and Markov Decision Problems Compared

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this