Exact stochastic constraint optimisation with applications in network analysis

Artificial Intelligence, vol. 304, pp. 103650

Abstract

We present an extensive study of methods for exactly solving stochastic constraint (optimisation) problems (SCPs) in network analysis. These problems are prevalent in science, governance and industry. The first method we study is generic and decomposes stochastic constraints into a multitude of smaller local constraints that are solved using a constraint programming (CP) or mixed-integer programming (MIP) solver. However, many SCPs are formulated on probability distributions with a monotonic property, meaning that adding a positive decision to a partial solution to the problem cannot cause a decrease in solution quality. The second method is specifically designed for solving global stochastic constraints on monotonic probability distributions (SCMDs) in CP. Both methods use knowledge compilation to obtain a decision diagram encoding of the relevant probability distributions, where we focus on ordered binary decision diagrams (OBDDs). We discuss theoretical advantages and disadvantages of these methods and evaluate them experimentally. We observed that global approaches to solving SCMDs outperform decomposition approaches from CP, and perform complementarily to MIP-based decomposition approaches, while scaling much more favourably with instance size. Both methods have many alternative design choices, as both knowledge compilation and constraint solvers are used in a single pipeline. To identify which configurations work best, we apply programming by optimisation. Specifically, we show how an automated algorithm configurator can be used to find optimised configurations of our pipeline. After configuration, our global SCMD solving pipeline outperforms its closest competitor (a MIP-based decomposition pipeline) on all test sets we considered by up to two orders of magnitude in terms of PAR10 scores.

Authors 6

1. Anna L. D. Latour corresponding Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands

2. Behrouz Babaki

   Polytechnique Montréal

   Affiliation as printed

   Polytechnique Montréal, Montréal (Québec), H3T 1J4, Canada

3. Daniël Fokkinga Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands

4. Marie Anastacio Aachen

   Leiden University

   Affiliation as printed

   LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands

5. Holger H. Hoos Aachen

   Leiden University · University of British Columbia

   Affiliation as printed

   LIACS, Leiden University, P.O. Box 9512, 2300 RA Leiden, the Netherlands

   University of British Columbia, Vancouver (British Columbia), V6T 1Z4, Canada

6. Siegfried Nijssen corresponding

   UCLouvain

   Affiliation as printed

   ICTEAM, UCLouvain, Place Sainte-Barbe 2 bte L5.02.01, B-1348 Louvain-la-Neuve, Belgium