Constraint-Based Multi-Objective Combinatorial Optimization


Miguel Terra-Neves


Instituto Superior Técnico, Universidade de Lisboa, Portugal


Vasco Manquinho
Inês Lynce


Multi-objective optimization problems are common in many real-world scenarios. One example is the virtual machine consolidation problem, where a cloud provider wishes to relocate virtual machines within a data center in order to reduce its energy consumption, but the new placement should not have a strong negative impact on the data center's performance. A plethora of techniques exist in the literature for optimizing multiple possibly conflicting objectives, mostly based on stochastic algorithms. These techniques are able to quickly find a high quality set of solutions. However, if the search space is tightly constrained, stochastic algorithms struggle to find a single solution that does not violate the problem's constraints. Moreover, these algorithms typically require a significant amount of tuning effort.

On the other hand, approaches that rely on constraint solvers thrive in scenarios where the search space is tightly constrained and are guaranteed to find solutions that satisfy the problem's constraints. Such approaches have been successfully applied to a wide range of single-objective optimization problems. Nevertheless, to the best of our knowledge, their application to multi-objective problems has not been properly explored in the literature, compared to stochastic algorithms. In this work, we propose several novel constraint-based approaches for multi-objective optimization, and show their merits through an extensive experimental evaluation on instances of the virtual machine consolidation problem. The evaluation shows that the new techniques enhance the state-of-the-art for solving multi-objective combinatorial optimization problems.


Tuesday, June 18, 2019