Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(4)
Decision Problem
Probability Distribution
Arc Consistency
Forward Checking
Related Publications
(1)
Stochastic Constraint Programming
Subscribe
Academic
Publications
Algorithms for Stochastic CSPs
Algorithms for Stochastic CSPs,10.1007/11889205_6,Thanasis Balafoutis,Kostas Stergiou
Edit
Algorithms for Stochastic CSPs
(
Citations: 13
)
BibTex

RIS

RefWorks
Download
Thanasis Balafoutis
,
Kostas Stergiou
The Stochastic CSP (SCSP) is a framework recently intro duced by Walsh to capture combinatorial decision problems that involve uncertainty and probabilities. The SCSP extends the classical CSP by including both decision variables, that an agent can set, and stochastic variables that follow a
probability distribution
and can model uncer tain events beyond the agent's control. So far, two approaches to solving SCSPs have been proposed; backtrackingbased procedures that extend standard methods from CSPs, and scenariobased methods that solve SCSPs by reducing them to a sequence of CSPs. In this paper we further investigate the former approach. We first identify and correct a flaw in the
forward checking
(FC) procedure proposed by Walsh. We also extend FC to better take advantage of probabilities and thus achieve stronger pruning. Then we define
arc consistency
for SCSPs and introduce an
arc consistency
algorithm that can handle constraints of any arity.
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 4458, 2006
DOI:
10.1007/11889205_6
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.springerlink.com
)
(
www.springerlink.com
)
(
www.icsd.aegean.gr
)
(
www.informatik.unitrier.de
)
(
dx.doi.org
)
(
www.icsd.aegean.gr
)
More »
Citation Context
(8)
...The Constraint Programming community is working on stochastic constraint satisfaction problems [5,
6
] to address, a.o., multiobjective decision making under uncertainty [7]...
Tino Teige
,
et al.
Generalized Craig Interpolation for Stochastic Boolean Satisfiability ...
...stochastic constraint satisfaction problems [5,6,
7
] to address, e.g., multiobjective decision making under uncertainty [8]...
Tino Teige
,
et al.
Resolution for Stochastic Boolean Satisfiability
...The domains of stochastic variable s1 ,s 3 ,s 5 ,s 7 contain 2 values while those of s2 ,s 4 ,s 6 ,s 8 contain 3 values; in both bases the values are chosen randomly from the discrete interval [
1
,5] and have equal probabilities...
...[20] presented two complete algorithms based on backtracking and forward checking and suggested some approximation procedures, while [
1
] described an arcconsistency algorithm...
Steven David Prestwich
,
et al.
Evolving Parameterised Policies for Stochastic Constraint Programming
...In this constraint, for the first scenario (s1 = a and s2 = a) the only consistent values for PT [0] and PT [
1
] are 1 and 2 respectively...
...For the second scenario (s1 = a and s2 = b) the only consistent values for PT [0] and PT [
1
] are 2 and 1 respectively...
...Our algorithm originally introduces three decision variables PT [0] ∈{ 1, 2}, PT [
1
] ∈{ 1, 2, 3} ,a ndPT [2] ∈{ 1, 2, 3}. Assume that at some Synthesizing Filtering Algorithms for Global ChanceConstraints 447...
...stage during search, the domains become PT [0] ∈{ 1, 2}, PT [
1
] ∈{ 1, 2} ,a nd PT [2] ∈{ 3}. In Table 1, the values that are not pruned by Algorithm 1 when θ =0 .75 are underlined...
...But, value 2 was providing support to value 1 in the domain of PT [
1
]...
...This goes undetected by the algorithm and value 1 for PT [
1
] no longer provides f [1 ,v ]=0 .25 satisfaction, but 0. Thus, there exists no satisfying policy in which PT [1] = 1! We can easily remedy this problem by repeatedly calling Algorithm 1 until we reach a fixedpoint and no further pruning is done...
...This goes undetected by the algorithm and value 1 for PT [1] no longer provides f [1 ,v ]=0 .25 satisfaction, but 0. Thus, there exists no satisfying policy in which PT [
1
] = 1! We can easily remedy this problem by repeatedly calling Algorithm 1 until we reach a fixedpoint and no further pruning is done...
...Other search and consistency strategies, namely a backtracking algorithm, a forward checking procedure [10] and an arcconsistency [
1
] algorithm have been proposed for SCSPs...
Brahim Hnich
,
et al.
Synthesizing Filtering Algorithms for Global ChanceConstraints
...Such an approach has been further investigated in [
3
]...
...Depending on the given problem and on the response policy chosen, dedicated efficient filtering algorithms can be implemented (see the forward checking technique proposed by Walsh [35 ]f orwaitandsee policies, and the improved algorithm in [
3
])...
...We focus on the (R n ,S n ) policy, which is hybrid and therefore cannot be solved by means of the approaches in [
3
, 33] that only cope with waitandsee policies...
Roberto Rossi
,
et al.
A Global ChanceConstraint for Stochastic Inventory Systems Under Serv...
References
(9)
CSP Properties for Quantified Constraints: Definitions and Complexity
(
Citations: 17
)
Lucas Bordeaux
,
Marco Cadoli
,
Toni Mancini
Conference:
National Conference on Artificial Intelligence  AAAI
, pp. 360365, 2005
Boolean and Interval Propagation for Quantified Constraints
(
Citations: 5
)
Lucas Bordeaux
Possibility Theory in Constraint Satisfaction Problems: Handling Priority, Preference and Uncertainty
(
Citations: 167
)
Didier Dubois
,
Hélène Fargier
,
Henri Prade
Journal:
Applied Intelligence  APIN
, vol. 6, no. 4, pp. 287309, 1996
Scenariobased Stochastic Constraint Programming
(
Citations: 24
)
Suresh Manandhar
,
Armagan Tarim
,
Toby Walsh
Conference:
International Joint Conference on Artificial Intelligence  IJCAI
, pp. 257262, 2003
Constraint Solving in Uncertain and Dynamic Environments: A Survey
(
Citations: 33
)
Gérard Verfaillie
,
Narendra Jussien
Journal:
Constraints  An International Journal  CONSTRAINTS
, vol. 10, no. 3, pp. 253281, 2005
Sort by:
Citations
(13)
Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems
Tino Teige
,
Martin Fränzle
Conference:
Tools and Algorithms for Construction and Analysis of Systems  TACAS
, pp. 158172, 2011
Resolution for Stochastic Boolean Satisfiability
(
Citations: 1
)
Tino Teige
,
Martin Fränzle
Conference:
Logic Programming and Automated Reasoning/Russian Conference on Logic Programming  LPAR(RCLP)
, pp. 625639, 2010
A Survey on CPAIOR Hybrids for Decision Making Under Uncertainty
(
Citations: 1
)
Brahim Hnich
,
Roberto Rossi
,
S. Armagan Tarim
,
Steven Prestwich
Published in 2010.
Evolving Parameterised Policies for Stochastic Constraint Programming
(
Citations: 2
)
Steven David Prestwich
,
S. Armagan Tarim
,
Roberto Rossi
,
Brahim Hnich
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 684691, 2009
Synthesizing Filtering Algorithms for Global ChanceConstraints
(
Citations: 2
)
Brahim Hnich
,
Roberto Rossi
,
S. Armagan Tarim
,
Steven David Prestwich
Conference:
Principles and Practice of Constraint Programming  CP
, pp. 439453, 2009