Joint Chance Constrained Probabilistic Simple Temporal Networks via Column Generation (Extended Abstract)

Authors

  • Andrew Murray University of Strathclyde
  • Michael Cashmore University of Strathclyde
  • Ashwin Arulselvan University of Strathclyde
  • Jeremy Frank NASA Ames Research Center

DOI:

https://doi.org/10.1609/socs.v15i1.21794

Keywords:

Constraint Search, Model-based Search, Bounding And Pruning Techniques, Time, Memory, And Solution Quality Trade-offs

Abstract

Probabilistic Simple Temporal Networks (PSTN) are used to represent scheduling problems under uncertainty. In a temporal network that is Strongly Controllable (SC) there exists a concrete schedule that is robust to any uncertainty. We solve the problem of determining Chance Constrained PSTN SC as a Joint Chance Constrained optimisation problem via column generation, lifting the usual assumptions of independence and Boole's inequality typically leveraged in PSTN literature. Our approach offers on average a 10 times reduction in cost versus previous methods.
SoCS 22 Cover

Downloads

Published

2022-07-17

How to Cite

Murray, A., Cashmore, M., Arulselvan, A., & Frank, J. (2022). Joint Chance Constrained Probabilistic Simple Temporal Networks via Column Generation (Extended Abstract). Proceedings of the International Symposium on Combinatorial Search, 15(1), 305–307. https://doi.org/10.1609/socs.v15i1.21794

Issue

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Section

Extended Abstracts