Multi-Objective Optimization Through Pareto Minimal Correction Subsets

Miguel Terra-Neves, Inês Lynce, Vasco ManquinhoIJCAI 2018 · DOI

TL;DR

This paper introduces Pareto Minimal Correction Subsets (Pareto-MCSs) as a novel way to approximate Pareto-optimal solutions for multi-objective optimization problems. By establishing an equivalence between Pareto-MCSs and Pareto-optimal solutions, and showing how Pareto-MCSs can be derived from standard Minimal Correction Subsets (MCSs), the authors provide an efficient, constraint-based approach that performs competitively with state-of-the-art evolutionary algorithms on a challenging real-world problem.

What Problem Does This Paper Address?

Many real-world decision-making scenarios involve optimizing multiple, often conflicting, objectives simultaneously. For instance, in cloud computing, one might want to minimize energy consumption while also minimizing the cost of migrating virtual machines. These problems typically have a set of "Pareto-optimal" solutions, where improving one objective necessitates worsening another. Finding this entire set of optimal trade-offs (the Pareto front) is computationally challenging, especially for large and complex problems. Existing methods, like evolutionary algorithms, are often non-deterministic and can struggle with tightly constrained problems. This paper aims to bridge this gap by proposing a new, constraint-based method for approximating Pareto-optimal solutions.

Methods

The core contribution is the introduction of Pareto Minimal Correction Subsets (Pareto-MCSs). This concept extends the idea of Minimal Correction Subsets (MCSs) from single-objective constraint satisfaction to multi-objective settings.

  • Minimal Correction Subset (MCS): In a set of constraints that cannot all be satisfied simultaneously, an MCS is the smallest subset of constraints that, if removed, makes the remaining set satisfiable. MCSs are useful for finding approximate solutions to single-objective optimization problems.
  • Multi-Objective Weighted Boolean Optimization (MOWBO): This is the formal framework used, involving hard constraints that must be satisfied and multiple sets of soft constraints, each with associated weights. The goal is to find assignments that satisfy all hard constraints and minimize the sum of weights of unsatisfied soft constraints across different objectives.
  • Multi-MCS: An extension of MCS to MOWBO, where a tuple of subsets of soft constraints (one subset per objective) is identified.
  • Pareto-MCS: A Multi-MCS that is not dominated by any other Multi-MCS, analogous to Pareto-optimal solutions.
  • Equivalence: The paper proves a crucial equivalence: Pareto-optimal solutions in MOWBO problems correspond directly to Pareto-MCSs. This means that finding Pareto-MCSs is equivalent to finding Pareto-optimal solutions.
  • Reduction to MCS: A key insight is that enumerating Pareto-MCSs can be reduced to enumerating standard MCSs. This allows leveraging existing, efficient MCS enumeration algorithms.

Datasets

The paper evaluates its approach on instances of the Virtual Machine Consolidation (VMC) problem. These instances are derived from subsets of workload traces from the Google Cluster Data project. The authors note that these benchmarks are publicly available. No new datasets were introduced.

Key Insights and Ideas

  • Pareto-MCS as a proxy for Pareto Front: The most significant insight is the formal equivalence established between Pareto-MCSs and Pareto-optimal solutions. This provides a novel, constraint-based perspective on multi-objective optimization.
  • Leveraging existing MCS solvers: The ability to reduce Pareto-MCS enumeration to standard MCS enumeration is a major practical advantage. It means researchers and practitioners can immediately benefit from years of development in efficient MCS solvers without needing to develop entirely new algorithms for the multi-objective case.
  • Robustness in constrained problems: The experimental results suggest that the Pareto-MCS approach (PCLD) is more robust than evolutionary algorithms when migration costs are constrained, indicating its strength in tightly constrained scenarios.

Key Results

The Pareto-MCS approach (referred to as PCLD) was evaluated against state-of-the-art evolutionary algorithms (VMPMBBO, MGGA, NSGAII) on Virtual Machine Consolidation instances.

  • High Migration Costs (bp = 100%): NSGAII performed best in terms of Hypervolume (HV) and Inverted Generational Distance (IGD) distributions, indicating it found good quality and diverse solution sets for more instances.
  • Low Migration Costs (bp = 5%, 1%): The performance of evolutionary algorithms degraded significantly, with MGGA failing to find feasible solutions for many instances. In contrast, PCLD remained robust, performing competitively and finding feasible solutions for more instances than the others.
  • Quality: PCLD was able to find feasible solutions for far more instances than the remaining algorithms under tighter migration budget constraints.

Limitations and Future Work

  • Computational Cost: While the paper demonstrates the competitiveness of Pareto-MCS, the exact computational cost of enumerating all Pareto-MCSs for very large problems is not explicitly detailed. The reduction to MCS enumeration implies that the complexity is tied to the underlying MCS solver.
  • Parameter Sensitivity: The paper mentions that evolutionary algorithms are parameter-sensitive. While PCLD leverages existing MCS solvers, the process of filtering dominated Multi-MCSs might introduce its own set of parameters or require careful tuning of the underlying MCS enumerator.
  • Future Work: The paper concludes by highlighting the effectiveness of the Pareto-MCS approach and its potential for approximating Pareto fronts. Future work could involve exploring more complex multi-objective problems and further optimizing the Pareto-MCS enumeration process.

Summary updated

BibTeX
@inproceedings{terraneves2018multi,
  author = {Miguel Terra-Neves and Inês Lynce and Vasco Manquinho},
  title = {{Multi-Objective Optimization Through Pareto Minimal Correction Subsets}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/757},
}
Figure