Finding (α, ϑ)-Solutions via Sampled SCSPs

Rossi, Roberto; Hnich, Brahim; Tarim, Armagan; Prestwich, Steven D.

doi:10.5591/978-1-57735-516-8/IJCAI11-362

Finding (α, ϑ)-Solutions via Sampled SCSPs

Roberto Rossi, Brahim Hnich, Armagan Tarim, Steven D. Prestwich

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2172-2176.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-362

Abstract

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.

Roberto Rossi, Brahim Hnich, Armagan Tarim, and Steven D. Prestwich. 2011. Finding (α, ϑ)-Solutions via Sampled SCSPs. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2172–2176. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-362

@inproceedings{ijcai2011p362,
  title     = {Finding (α, ϑ)-Solutions via Sampled SCSPs},
  author    = {Rossi, Roberto and Hnich, Brahim and Tarim, Armagan and Prestwich, Steven D.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2172--2176},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-362},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-362},
}

TY  - CPAPER
TI  - Finding (α, ϑ)-Solutions via Sampled SCSPs
AU  - Rossi, Roberto
AU  - Hnich, Brahim
AU  - Tarim, Armagan
AU  - Prestwich, Steven D.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2172
EP  - 2176
DO  - 10.5591/978-1-57735-516-8/IJCAI11-362
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-362
ER  -