Joint chance constrained probabilistic simple temporal networks via column generation

Andrew Murray; Michael Cashmore; Ashwin Arulselvan; Jeremy Frank

Joint chance constrained probabilistic simple temporal networks via column generation

Andrew Murray, Michael Cashmore, Ashwin Arulselvan, Jeremy Frank

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution book

25 Downloads (Pure)

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.

Original language	English
Title of host publication	15th International Symposium on Combinatorial Search
Place of Publication	California, USA
Pages	305-307
Number of pages	3
Publication status	Published - 18 Jul 2022

Keywords

Probabilistic Simple Temporal Networks (PSTN)
uncertainty
Boole’s inequality

Access to Document

Murray-etal-SOCS2022-Joint-chance-constrained-probabilistic-simple-temporal-networksAccepted author manuscript, 725 KBLicence: Strath_1

Cite this

@inproceedings{24e4d2ddc03c4af59bcee3097f0d7760,

title = "Joint chance constrained probabilistic simple temporal networks via column generation",

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{\textquoteright}s inequality typically leveraged in PSTN literature. Our approach offers on average a 10 times reduction in cost versus previous methods.",

keywords = "Probabilistic Simple Temporal Networks (PSTN), uncertainty, Boole{\textquoteright}s inequality",

author = "Andrew Murray and Michael Cashmore and Ashwin Arulselvan and Jeremy Frank",

year = "2022",

month = jul,

day = "18",

language = "English",

isbn = "1577358732",

pages = "305--307",

booktitle = "15th International Symposium on Combinatorial Search",

}

TY - GEN

T1 - Joint chance constrained probabilistic simple temporal networks via column generation

AU - Murray, Andrew

AU - Cashmore, Michael

AU - Arulselvan, Ashwin

AU - Frank, Jeremy

PY - 2022/7/18

Y1 - 2022/7/18

N2 - 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.

AB - 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.

KW - Probabilistic Simple Temporal Networks (PSTN)

KW - uncertainty

KW - Boole’s inequality

UR - https://ojs.aaai.org/index.php/SOCS/issue/view/524

M3 - Conference contribution book

SN - 1577358732

SP - 305

EP - 307

BT - 15th International Symposium on Combinatorial Search

CY - California, USA

ER -

Joint chance constrained probabilistic simple temporal networks via column generation

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this