Enhancing Constraint-Based Multi-Objective Combinatorial Optimization

Authors

  • Miguel Terra-Neves INESC-ID / Instituto Superior Técnico, Universidade de Lisboa, Portugal
  • Inês Lynce INESC-ID / Instituto Superior Técnico, Universidade de Lisboa, Portugal
  • Vasco Manquinho INESC-ID / Instituto Superior Técnico, Universidade de Lisboa, Portugal

Keywords:

Multi-Objective Combinatorial Optimization, Minimal Correction Subsets

Abstract

Minimal Correction Subsets (MCSs) have been successfully applied to find approximate solutions to several real-world single-objective optimization problems. However, only recently have MCSs been used to solve Multi-Objective Combinatorial Optimization (MOCO) problems. In particular, it has been shown that all optimal solutions of MOCO problems with linear objective functions can be found by an MCS enumeration procedure. In this paper, we show that the approach of MCS enumeration can also be applied to MOCO problems where objective functions are divisions of linear expressions. Hence, it is not necessary to use a linear approximation of these objective functions. Additionally, we also propose the integration of diversification techniques on the MCS enumeration process in order to find better approximations of the Pareto front of MOCO problems. Finally, experimental results on the Virtual Machine Consolidation (VMC) problem show the effectiveness of the proposed techniques.

Downloads

Published

2018-04-26

How to Cite

Terra-Neves, M., Lynce, I., & Manquinho, V. (2018). Enhancing Constraint-Based Multi-Objective Combinatorial Optimization. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12212

Issue

Section

Main Track: Search and Constraint Satisfaction