turkmath.org

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 traditional constraint optimization techniques, for example constraints programming, mathematical programming, optimization modulo theory, and the application of suitable symmetry breakers to overcome 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:

· the symmetries of the underlying problem (Cloud deployment of component-based applications),

· the graph representation associated to the structural constraints specific to each particular application, and

· 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 column-wise 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, on one hand, the number of added constraints which influences the solving time, on the other hand, the symmetry breakers can interact badly with the underlying optimization techniques implemented by the solvers we used.