Stratification for Constraint-Based Multi-Objective Combinatorial Optimization

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

TL;DR

This paper introduces "stratification" as a novel technique to improve constraint-based algorithms for Multi-Objective Combinatorial Optimization (MOCO). By strategically partitioning and processing problem constraints, their method achieves competitive performance with state-of-the-art stochastic algorithms, particularly in challenging, tightly constrained scenarios.

What Problem Does This Paper Address?

Multi-Objective Combinatorial Optimization (MOCO) problems involve finding solutions that simultaneously optimize multiple, often conflicting, objectives. The set of all such optimal solutions is known as the Pareto front. While stochastic algorithms are good at approximating Pareto fronts for loosely constrained problems, they struggle when constraints become difficult to satisfy. Conversely, constraint-based methods excel at handling complex constraints but have historically had difficulty in effectively integrating multiple objectives to produce diverse and high-quality Pareto front approximations. This paper aims to bridge this gap by enhancing constraint-based MOCO solvers with a technique that leverages problem structure to improve both efficiency and solution quality.

Methods

The core contribution of this paper is the introduction and formalization of stratification for constraint-based MOCO algorithms. Stratification, previously used in single-objective optimization (like MaxSAT), involves partitioning the problem's constraints (specifically, the "soft" constraints or those related to objectives) into ordered groups based on some criteria (e.g., coefficient magnitude).

The proposed approach, Stratified MCS-based MOCO (SCLD), works as follows:

  1. Partitioning: For each objective function, the set of literals that would violate it (represented as "negated literals" or $\bar{L}(f_i)$) are partitioned into ordered sets ($P_1, P_2, \dots, P_k$). This ordering is typically based on the magnitude of the coefficients associated with these literals in the objective function.
  2. Combining Partitions: These partitions from different objectives are then combined into a single sequence of partitions.
  3. Iterative MCS Computation: The algorithm iteratively computes Minimal Correction Subsets (MCSs). An MCS is a minimal set of constraints that, when removed, makes an unsatisfiable set of constraints satisfiable. In this context, MCSs are used to find solutions that satisfy the hard constraints and minimize the impact of the soft constraints. The algorithm processes the combined partitions sequentially, adding previously satisfied constraints and negations of violated constraints to the set of hard constraints for the next iteration. This process guides the search towards solutions that address objectives with higher-priority literals first.
  4. Division Reduction Handling: The paper also addresses a specific challenge in MOCO: "division reduction," a technique used for certain cost functions. They propose two strategies, MERGE and SPLIT, to handle this, with MERGE showing superior performance in finding more MCSs.

The paper also introduces and evaluates two partitioning heuristics: FIXED (splitting into a fixed number of partitions) and Literal-Weight Ratio (LWR), which is proposed as a variant of a previous heuristic. LWR is shown to be more effective.

Datasets

The evaluation was performed on publicly available Virtual Machine Consolidation (VMC) problem instances. These benchmarks are based on subsets of workload traces from the Google Cluster Data project. The paper notes that the resource wastage cost function in VMC is a sum of divisions, making it a suitable testbed for their division reduction handling strategies.

Key Insights and Ideas

  • Stratification as a unifying principle: The paper demonstrates that stratification, a technique previously successful in single-objective constraint solving, can be effectively adapted to guide multi-objective constraint-based solvers.
  • Addressing the constraint-difficulty trade-off: The core insight is that by stratifying constraints, constraint-based methods can overcome their historical weakness in handling multiple objectives, especially when problems become tightly constrained, a scenario where stochastic methods falter.
  • LWR heuristic's effectiveness: The proposed Literal-Weight Ratio (LWR) partitioning heuristic significantly outperforms the simpler FIXED heuristic, suggesting that intelligently grouping literals based on their impact on objectives is crucial.
  • MERGE strategy's advantage: For problems involving division reduction, the MERGE strategy for combining partitions proved much more effective than the SPLIT strategy in generating a larger number of MCSs, indicating better exploration of the solution space.
  • Competitive performance: The stratified approach (SCLD) achieves performance comparable to, and in some cases better than, state-of-the-art stochastic algorithms, particularly in scenarios with tight constraints.

Key Results

  • Partitioning Heuristics: The LWR heuristic consistently outperformed the FIXED heuristic in terms of both Hypervolume (HV) and Inverted Generational Distance (IGD) indicators.
  • Division Reduction: The MERGE strategy was significantly better than SPLIT at finding a larger number of MCSs, suggesting it explores the solution space more effectively.
  • Comparison with State-of-the-Art:
    • Constraint-based: SCLD showed a "huge performance improvement" compared to previous constraint-based MOCO algorithms (CLD and MCSEnumPD).
  • Stochastic: For VMC instances with a 100% migration budget (loosely constrained), SCLD was competitive with stochastic algorithms (NSGAII, MOEAD, VMPMBBO) in HV, but stochastic methods achieved better IGD.
  • Tightly Constrained Scenarios: As migration budgets decreased (bp = 5% and 1%), stochastic algorithms' performance degraded significantly, while SCLD maintained its competitiveness and was the best performing algorithm when bp ≤ 5%.

Limitations and Future Work

  • Limitations:
    • The paper notes that while SCLD finds approximations with higher diversity (indicated by better HV), stochastic algorithms sometimes achieve better convergence (indicated by better IGD).
  • For very large MOCO instances, enumerating the complete Pareto front is still infeasible. The goal is to find a diverse set of good quality solutions within a time limit.
  • Future Work:
    • Improve diversity by dynamically adapting cost function selection probabilities.
  • Incorporate user preferences into the optimization process.
  • Explore combining stochastic and constraint-based methods for MOCO, aiming to leverage the strengths of both worlds.

Summary updated

BibTeX
@inproceedings{terraneves2018stratification,
  author = {Miguel Terra-Neves and Inês Lynce and Vasco Manquinho},
  title = {{Stratification for Constraint-Based Multi-Objective Combinatorial Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/191},
}
Figure