ECAI Conference 2014 Conference Paper
Symmetry Breaking for Exact Solutions in Adjustable Robust Optimisation
- Steven D. Prestwich
- Marco Laumanns
- Ban Kawas
One of the key unresolved challenges in Adjustable Robust Optimisation is how to deal with large discrete uncertainty sets. In this paper we present a technique for handling such sets based on symmetry breaking ideas from Constraint Programming. In earlier work we applied the technique to a pre-disaster planning problem modelled as a two-stage Stochastic Program, and we were able to solve exactly instances that were previously considered intractable and only had approximate solutions. In this paper we show that the technique can also be applied to an adjustable robust formulation that scales up to larger instances than the stochastic formulation. We also describe a new fast symmetry breaking heuristic that gives improved results.