Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract)

Murray, Andrew and Cashmore, Michael and Arulselvan, Ashwin (2022) Joint chance constrained probabilistic simple temporal networks via column generation (extended abstract). In: 19th International Conference on the Integration of Constraint Programmng, Artificial Intelligence, and Operations Research, 2022-06-20 - 2022-06-23, https://sites.google.com/usc.edu/cpaior-2022.

[thumbnail of Murray-etal-CPAIOR-2022-Joint-chance-constrained-probabilistic-simple-temporal-networks-via-column-generation]
Preview
 Text. Filename: Murray_etal_CPAIOR_2022_Joint_chance_constrained_probabilistic_simple_temporal_networks_via_column_generation.pdf
Accepted Author Manuscript
License: Strathprints license 1.0
Download (660kB)| 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. In this paper we introduce the Joint Chance-Constrained PSTN (JCC-PSTN) which lifts assumptions of independence and Boole's inequality, which are typically leveraged in PSTN literature. We solve the problem of JCC-PSTN SC via a column generation procedure and find that our approach offers on average a 10 times reduction in cost versus using Boole’s inequality.

CORE (COnnecting REpositories)