Mădălina Erascu
West University of Timişoara, Timişoara, Romania

Constraint optimization, symmetries and symmetry breaking have long been studied by mathematicians. Despite this, when it comes to apply them to real-world problems, for example the deployment in the Cloud of the component-based applications, challenges appear. One such challenge is the scalability issue of general constraint optimization techniques, for example constraints programming, mathematical programming, optimization modulo theory, and the application of suitable symmetry breakers to deal with this issue. We overcome it by methodologically analyzing the particularities of the problem to be solved with the aim of identifying search space reduction methods. These are methods exploiting:
(1) the symmetries of the underlying problem (Cloud deployment of component-based applications),
(2) the graph representation associated to the structural constraints specific to each particular application, and
(3) their combination.

An extensive experimental analysis has been conducted on 4 classes of real-world problems, using 19 symmetry breaking strategies and 3 types of optimization solvers. As a result, the combination of two symmetry breakers, a variable reduction strategy with a columnwise symmetry breaker, led to a scalable deployment. However, one would expect that the best symmetry breaker is one composing a higher number of individual symmetry breakers as more symmetries are broken so the search space is significantly reduced. The experiments proved that this is not true. An explanation is that, on one hand, the large number of added constraints influences the solving time, and, on the other hand, the symmetry breakers interact badly with the underlying optimization techniques implemented by the solvers we used.
This is joint work with Bogdan David, Flavia Micota and Daniela Zaharie.