Programming a Stochastic Constraint Optimisation Algorithm, by Optimisation
Stochastic Constraint Optimisation Problems (SCOPs), such as the viral marketing problem and transmission grid reliability problem, arise in fields such as industry, governance and science. The recently proposed Stochastic Constraint Probabilistic Prolog (SC-ProbLog) language makes it possible to model and solve such SCOPs. Solving SCOPs exactly is NP-hard, and to solve real-world problems, exact SCOP solving methods must employ highly optimised heuristics. We propose to follow the principle of Programming by Optimisation (PbO): we expose the design choices of a recently proposed SCOP solving method and optimise these using Automated Algorithm Configuration (AAC). For a set of viral marketing problems, our optimised SCOP solver runs up to 26 times faster and solves almost two thirds of the instances that could not be solved within a cutoff time of ten minutes, by an expert-chosen default configuration of the solver. For a set of transmission grid reliability problems, the optimised configuration solves ten percent more instances overall, and solves some instances up to ten times faster.
Published in Workshop Data Science meets Optimisation (DSO), held in conjunction with IJCAI 2019, 2019