Academic
Publications
Algorithms for Stochastic CSPs

Algorithms for Stochastic CSPs,10.1007/11889205_6,Thanasis Balafoutis,Kostas Stergiou

Algorithms for Stochastic CSPs   (Citations: 13)
BibTex | RIS | RefWorks Download
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; backtracking-based procedures that extend standard methods from CSPs, and scenario-based 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.
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.
    • ...The Constraint Programming community is working on stochastic constraint satisfaction problems [5,6] to address, a.o., multi-objective decision making under uncertainty [7]...

    Tino Teigeet al. Generalized Craig Interpolation for Stochastic Boolean Satisfiability ...

    • ...stochastic constraint satisfaction problems [5,6,7] to address, e.g., multi-objective decision making under uncertainty [8]...

    Tino Teigeet 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 arc-consistency algorithm...

    Steven David Prestwichet 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 Chance-Constraints 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 fixed-point 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 fixed-point and no further pruning is done...
    • ...Other search and consistency strategies, namely a backtracking algorithm, a forward checking procedure [10] and an arc-consistency [1] algorithm have been proposed for SCSPs...

    Brahim Hnichet al. Synthesizing Filtering Algorithms for Global Chance-Constraints

    • ...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 orwait-and-see 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 wait-and-see policies...

    Roberto Rossiet al. A Global Chance-Constraint for Stochastic Inventory Systems Under Serv...

Sort by: