Flow-Based Combinatorial Chance Constraints.pdf.pdf' (171.45 kB)

Flow-Based Combinatorial Chance Constraints

Download (171.45 kB)
journal contribution
posted on 13.03.2012, 00:00 by Andre A. Cire, Elvin Coban, Willem-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.

History

Publisher Statement

All Rights Reserved

Date

13/03/2012

Usage metrics

Exports