Automated deployment of component-based applications in the Cloud became important with the increased digital market demand. It consists of: (1) selection of the computing resources, (2) distribution/assignment of the application components over the available computing resources, (3) its dynamic modification to cope with peaks of user requests. We focus on the first two steps which can be formulated as a linear constraint optimization problem (COP) and solved using existing exact general techniques, such as constraint programming (CP), mathematical programming (MP), and optimization modulo theory (OMT). However, the computational requirement is high, making the problem impossible to be solved. We solved the issue by using static symmetry breaking techniques problem-tailored.