Joint chance constrained probabilistic simple temporal networks via column generation

Murray, Andrew and Cashmore, Michael and Arulselvan, Ashwin and Frank, Jeremy; (2022) Joint chance constrained probabilistic simple temporal networks via column generation. In: 15th International Symposium on Combinatorial Search. Association for the Advancement of Artificial Intelligence, California, USA, pp. 305-307. ISBN 1577358732

[thumbnail of Murray-etal-SOCS2022-Joint-chance-constrained-probabilistic-simple-temporal-networks]
Preview
 Text. Filename: Murray_etal_SOCS2022_Joint_chance_constrained_probabilistic_simple_temporal_networks.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (742kB)| Preview

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.

ORCID iDs

Murray, Andrew, Cashmore, Michael ORCID logoORCID: https://orcid.org/0000-0002-8334-4348, Arulselvan, Ashwin ORCID logoORCID: https://orcid.org/0000-0001-9772-5523 and Frank, Jeremy;
CORE (COnnecting REpositories)