Carnegie Mellon University
Flow-Based Combinatorial Chance Constraints.pdf.pdf' (171.45 kB)
Download file

Flow-Based Combinatorial Chance Constraints

Download (171.45 kB)
journal contribution
posted on 2012-03-13, 00:00 authored by Andre A. Cire, Elvin Coban, Willem-Jan Van HoeveWillem-Jan Van Hoeve

We study stochastic variants of flow-based global constraints as combinatorial chance constraints. As a specific case study, we focus on the stochastic weighted alldifferent constraint. We first show that determining the consistency of this constraint is NP-hard. We then show how the combinatorial structure of the all different constraint can be used to define chance-based filtering, and to compute a policy. Our propagation algorithm can be extended immediately to related flow-based constraints such as the weighted cardinality constraint. The main benefits of our approach are that our chance-constrained global constraints can be integrated naturally in classical deterministic CP systems, and are more scalable than existing approaches for stochastic constraint programming.


Publisher Statement

All Rights Reserved



Usage metrics