Joint Chance Constrained Probabilistic Simple Temporal Networks via Column Generation (Extended Abstract)
Keywords:Constraint Search, Model-based Search, Bounding And Pruning Techniques, Time, Memory, And Solution Quality Trade-offs
AbstractProbabilistic 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.