Finding (α, υ)-solutions via sampled SCSPs

Rossi R., Hnich B., TARIM Ş. A., Prestwich S.

22nd International Joint Conference on Artificial Intelligence, IJCAI 2011, Barcelona, İspanya, 16 - 22 Temmuz 2011, ss.2172-2177 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.5591/978-1-57735-516-8/ijcai11-362
  • Basıldığı Şehir: Barcelona
  • Basıldığı Ülke: İspanya
  • Sayfa Sayıları: ss.2172-2177
  • Hacettepe Üniversitesi Adresli: Evet

Özet

We discuss a novel approach for dealing with single-stage stochastic constraint satisfaction problems (SCSPs) that include random variables over a continuous or large discrete support. Our approach is based on two novel tools: sampled SCSPs and (α, υ)-solutions. Instead of explicitly enumerating a very large or infinite set of future scenarios, we employ statistical estimation to determine if a given assignment is consistent for a SCSP. As in statistical estimation, the quality of our estimate is determined via confidence interval analysis. In contrast to existing approaches based on sampling, we provide likelihood guarantees for the quality of the solutions found. Our approach can be used in concert with existing strategies for solving SCSPs.