Confidence-based reasoning in stochastic constraint programming

Roberto Rossi, Brahim Hnich, S Armagan Tarim, Steven Prestwich

Research output: Contribution to journalArticlepeer-review

Abstract

In this work we introduce a novel approach, based on sampling, for finding assignments that are likely to be solutions to stochastic constraint satisfaction problems and constraint optimisation problems. Our approach reduces the size of the original problem being analysed; by solving this reduced problem, with a given confidence probability, we obtain assignments that satisfy the chance constraints in the original model within prescribed error tolerance thresholds. To achieve this, we blend concepts from stochastic constraint programming and statistics. We discuss both exact and approximate variants of our method. The framework we introduce can be immediately employed in concert with existing approaches for solving stochastic constraint programs. A thorough computational study on a number of stochastic combinatorial optimisation problems demonstrates the effectiveness of our approach.
Original languageEnglish
Pages (from-to)129-152
Number of pages53
JournalArtificial Intelligence
Volume228
Early online date15 Jul 2015
DOIs
Publication statusPublished - Nov 2015

Keywords

  • confidence-based reasoning
  • stochastic constraint programming
  • sampled SCSP
  • (α,ϑ)-solution
  • (α,ϑ)-solution set
  • confidence interval

Fingerprint

Dive into the research topics of 'Confidence-based reasoning in stochastic constraint programming'. Together they form a unique fingerprint.

Cite this