Multi-Objective Optimization Through Pareto Minimal Correction Subsets

1 Introduction

Given an unsatisfiable set of constraints F , a Minimal Correction Subset (MCS) is a minimal subset of constraints C such that, if all constraints in C are removed from F, then F becomes satisfiable. MCSs enjoy a wide range of applications, such as analysis of over-constrained systems [Felfernig et al., 2012; Junker, 2004], minimal model computation [BenEliyahu and Dechter, 1996], interactive constraint satisfaction [O'Callaghan et al., 2005], among others [Menc´ıa et al., 2015]. Many efficient MCS enumeration algorithms have been recently proposed [Bacchus et al., 2014; Felfernig et al., 2012; Marques-Silva et al., 2013], and MCS-based approximation algorithms are able to find good quality approximations of optimal solutions efficiently [Menc´ıa et al., 2015].

∗This paper is an abridged version of the paper entitled "Introducing Pareto Minimal Correction Subsets" that won a best student paper award at the 20th International Conference on Theory and Applications of Satisfiability Testing [Terra-Neves et al., 2017]. For the interested reader, proofs of theoretical results presented throughout the paper are available in the full version.

However, the usage of MCSs has focused only on approximating single-objective problems.

In many scenarios, such as scheduling [Iturriaga et al., 2017] or green computing [Zheng et al., 2016], a decision maker may need to optimize multiple conflicting objectives [Ulungu and Teghem, 1994]. In this case, multiple optimal solutions may exist, referred to as Pareto-optimal solutions [Pareto, 1906], each of them favoring certain objectives at the expense of others. There is a wide plethora of stochastic algorithms that try to approximate the Pareto front [Deb et al., 2000; Xu and Fortes, 2010]. Such approaches are nondeterministic and are known to be parameter sensitive, resulting in each different problem requiring a distinct configuration of the algorithm to achieve a competitive performance. Moreover, stochastic algorithms are known to struggle as instances become more tightly constrained. On the other hand, it is widely accepted that constraint-based methods, compared to other approaches, usually thrive in tightly constrained problems, and some exact algorithms exist for computing the set of Pareto-optimal solutions of multi-objective problems [Rayside et al., 2009]. However, such solutions are impractical for large scale instances.

The main contributions of this paper are: (1) a first definition of Multi-MCSs and Pareto-MCSs, an extension of MCSs to constrained multi-objective optimization problems; (2) a proof of an equivalence relationship between Pareto-MCSs and Pareto-optimal solutions; (3) a proof of a relationship between Multi-MCSs and MCSs that allows one to use off-theshelf MCS enumerators as Multi-MCS enumerators; (4) an extensive experimental evaluation on virtual machine consolidation instances from the Google Cluster Data project which clearly shows the suitability of the Pareto-MCS approach for finding good quality approximations of the Pareto front.

The paper is organized as follows. Section 2 introduces basic definitions used in the remainder of the paper. In section 3, a definition of Multi-MCSs and Pareto-MCSs is proposed and some of their properties are described. Experimental results showing the effectiveness of the Pareto-MCS approach are presented in section 4. Section 5 concludes the paper.

2 Preliminaries

In this section, we introduce the necessary definitions and notations that will be used throughout the rest of the paper. We start by describing Weighted Boolean Optimization (WBO)

and its multi-objective version. Next, Minimal Correction Subsets (MCSs) are defined and we review how these can be used to find solutions for WBO problems.

2.1 Weighted Boolean Optimization

Let X = {x1, x2, . . . , xn} be a set of n Boolean variables. A literal is either a variable xi or its complement ¬xi. Given an integer k ∈ N, a set of m literals l1, l2, . . . , lm and their respective coefficients ω1, ω2, . . . , ωm ∈ N, a Pseudo-Boolean (PB) constraint is a linear inequality with the form:

A weighted PB constraint is a pair (c, ω), where c is a PB constraint and ω ∈ N+ is the cost of not satisfying c.

Given a formula F = (FH, FS), where FH and FS denote sets of hard and soft weighted PB constraints respectively, the WBO problem [Manquinho et al., 2009] consists of finding a complete assignment α : X → {0, 1} that satisfies all constraints in FH, denoted α(FH) = 1, and minimizes the sum of the weights of the constraints in FS that are not satisfied. If FH is unsatisfiable, we say that α(FH) = 0 for any assignment α. Analogously, given a PB constraint c, α(c) = 1 (α(c) = 0) denotes that α satisfies (does not satisfy) c.

Example 2.1. Let FH = {(x1 + x2 + x3 ≤ 2)} be the set of hard PB constraints and FS = {(x1 ≥ 1, 4), (x2 ≥ 1, 2), (x3 ≥ 1, 3)} the set of weighted soft PB constraints of a WBO instance. α1 = {(x1, 1), (x2, 0), (x3, 1)} is an optimal assignment that does not satisfy (x2 ≥ 1), having a cost of 2. α2 = {(x1, 0), (x2, 1), (x3, 1)} is not optimal because it does not satisfy (x1 ≥ 1), which has a weight of 4. α3 = {(x1, 1), (x2, 1), (x3, 1)} is an invalid assignment because it does not satisfy FH.

A Multi-Objective Weighted Boolean Optimization (MOWBO) instance is composed of a set FH of hard PB constraints and a set OS = {FS1, FS2, . . . , FSl} of soft weighted PB constraint sets. Given an assignment α and a set FSi ∈ OS, let w(FSi, α) denote the sum of the weights of the PB constraints in FSi unsatisfied by α, i.e.,

Definition 2.1. Let W = (FH,OS) be a MOWBO instance, with OS = {FS1, FS2, . . . , FSl}. Let α, α′ : X → {0, 1} be two complete assignments such that α ̸= α′ and α(FH) = α′ (FH) = 1. We say that α dominates α′ (α ≺ α′ ) if, and only if, ∀FS∈OS w(FS, α) ≤ w(FS, α′ ) and ∃F ′S ∈OS w(F ′S , α) < w(F ′S , α′ ).

Definition 2.2. Let W = (FH,OS) be a MOWBO instance and α : X → {0, 1} a complete assignment. α is Paretooptimal if, and only if, α(FH) = 1 and no other complete assignment α′ exists such that α′ (FH) = 1 and α′ ≺ α.

In MOWBO, the goal is to find the set of Paretooptimal [Pareto, 1906] solutions, i.e., the Pareto front.

Example 2.2. Let FH = {(x1 + x2 ≤ 1)} be the set of PB constraints and OS = {FS1, FS2}, where FS1 = {(¬x1, 1), (x2, 2)} and FS2 = {(x1, 1)}, the set of soft constraint sets of a MOWBO instance. Table 1 shows the costs for each possible assignment. Note that {(x1, 1), (x2, 1)} violates FH. Hence, it is not a valid assignment. {(x1, 0), (x2, 0)} is not Pareto-optimal because it is dominated by {(x1, 0), (x2, 1)}. However, {(x1, 0), (x2, 1)} and {(x1, 1), (x2, 0)} are Pareto-optimal solutions since they are not dominated by any other assignment that satisfies FH.

2.2 Minimal Correction Subsets

Given an unsatisfiable set of PB constraints F, an MCS is a minimal subset C ⊆ F such that F \ C is satisfiable.

Definition 2.3. Let F be an unsatisfiable set of constraints. A subset C ⊆ F is an MCS of F if, and only if, F \ C is satisfiable and (F \ C) ∪ {c} is unsatisfiable for all c ∈ C.

Example 2.3. Consider the unsatisfiable set of PB constraints F = {(x1 +x2 = 1), (x1 ≥ 1), (x2 ≥ 1)}. F has three MCSs C1 = {(x1 ≥ 1)}, C2 = {(x2 ≥ 1)} and C3 = {(x1 + x2 = 1)}.

Several algorithms exist for finding MCSs [Bailey and Stuckey, 2005; Felfernig et al., 2012; Marques-Silva et al., 2013; Menc´ıa et al., 2015]. The following definition extends the notion of MCS to WBO instances. For simplicity, we assume that the set of hard PB constraints FH of a WBO instance is always satisfiable, but this can be checked using a single call to a satisfiability solver.

Definition 2.4. Let F = (FH, FS) be aWBO instance, where FH and FS denote the hard and soft PB constraint sets respectively. A subset C ⊆ FS is an MCS of F if, and only if, FH ∪ (FS \ C) is satisfiable and FH ∪ (FS \ C) ∪ {c} is unsatisfiable for all c ∈ C.

An MCS provides an approximation to a WBO optimal solution, and in some problems is faster to compute [Ignatiev et al., 2014]. Actually, the WBO problem can be reduced to finding the MCS C ⊆ FS that minimizes the sum of the weights of its constraints [Birnbaum and Lozinskii, 2003].

Example 2.4. Consider the WBO instance given by FH = {(x1 + x2 = 1)} and FS = {(x1 ≥ 1, 1), (x2 ≥ 1, 2), (¬x1 ≥ 1, 4), (¬x2 ≥ 1, 6)}. It has two MCSs C1 = {(x1 ≥ 1, 1), (¬x2 ≥ 1, 6)} and C2 = {(x2 ≥ 1, 2), (¬x1 ≥ 1, 4)}. The sum of the weights of the constraints in C1 and C2 is 7 and 6 respectively. C2 is the MCS that minimizes the sum of the weights of its constraints. Therefore, any assignment that satisfies {(x1 + x2 = 1), (x1 ≥ 1), (¬x2 ≥ 1)} is an optimal solution of the WBO instance.

3 ParetoMinimal Correction Subsets

This section introduces the novel concept of Multi-MCSs and explains how they can be used to approximate the Pareto front of a MOWBO instance. First, Multi-MCSs and Pareto-MCSs are defined. Next, we describe some properties of MultiMCSs and Pareto-MCSs.

3.1 Multi and ParetoMinimal Correction Subsets

The definition of Multi-MCS, an extension of MCSs to MOWBO formulas, builds upon the concept of MCS for WBO formulas (see section 2.2).

Definition 3.1. Let W = (FH,OS) be a MOWBO instance, with OS = {FS1, FS2, . . . , FSl}. Let C = (C1, C2, . . . , Cl) be a tuple of sets such that Ci ⊆ FSi, 1 ≤ i ≤ l. C is a Multi-MCS of W if, and only if, FH ∪ ⋃li=1 (FSi \ Ci) is satisfiable and FH ∪ ⋃li=1 (FSi \ Ci) ∪ {c} is unsatisfiable for all c ∈ ⋃li=1 Ci.

The dominance relation between two MOWBO solutions in definition 2.1 can also be extended to pairs of Multi-MCSs.

Definition 3.2. Let W = (FH,OS) be a MOWBO instance. Let C = (C1,C2, . . . ,Cl) and C′ = (C ′1 ,C ′2 , . . . ,C ′ l ) be two Multi-MCSs of W. We say that C dominates C′ (C ≺ C′ ) if, and only if, ∀1≤i≤l ∑(c,ω)∈Ci ω ≤ ∑(c′ ,ω′ )∈C′ i ω′ and ∃1≤j≤l ∑(c,ω)∈Cj ω < ∑(c′ ,ω′ )∈C′j ω′ .

Considering the definition of dominance for Multi-MCSs, the concept of Pareto-MCS can be formalized.

Definition 3.3. Let W = (FH,OS) be a MOWBO instance and C a Multi-MCS of W. C is a Pareto-MCS if, and only if, no other Multi-MCS C′ exists such that C′ ≺ C.

Example 3.1. Recall the MOWBO instance W = (FH,OS) from example 2.2, with FH = {(x1 + x2 ≤ 1)} and OS = {FS1, FS2}, where FS1 = {(¬x1, 1), (x2, 2)} and FS2 = {(x1, 1)}. W has two Multi-MCSs C1 = ({}, {(x1, 1)}) and C2 = ({(¬x1, 1), (x2, 2)}, {}), which are also Pareto-MCSs.

3.2 Properties of Multi and ParetoMinimal Correction Subsets

Recall from section 2.2 that the WBO problem can be reduced to finding an MCS that minimizes the sum of the weights of its soft constraints. Therefore, it is expected that a MOWBO instance can be reduced to finding the set of its Pareto-MCSs. The following results reveal an equivalence relationship between Pareto-MCSs and Pareto-optimal solutions.

Proposition 1. Let W = (FH,OS) be a MOWBO instance, with OS = {FS1, FS2, . . . , FSl}, and α a Pareto-optimal solution of W. Let C = (C1, C2, . . . , Cl), where Ci = {(c, ω) : (c, ω) ∈ FSi ∧ α(c) = 0} for all 1 ≤ i ≤ l. Then, C is a Pareto-MCS of W.

Proposition 2. Let W = (FH,OS) be a MOWBO instance, with OS = {FS1, FS2, . . . , FSl}, and C = (C1, C2, . . . , Cl) a Pareto-MCS of W. Then, any complete assignment α that satisfies FH ∪ ⋃li=1 (FSi \ Ci) is a Pareto-optimal solution.

Propositions 1 and 2 show that for each Pareto-MCS there is at least one Pareto-optimal solution and that each Paretooptimal solution has an associated Pareto-MCS. Therefore, MOWBO can be reduced to Pareto-MCS enumeration in the same way that WBO can be reduced to MCS enumeration.

Proposition 3. Let W = (FH,OS) be a MOWBO instance, with OS = {FS1, FS2, . . . , FSl}, and C = (C1, C2, . . . , Cl) a Multi-MCS of W. Then, C = ⋃li=1 Ci is an MCS of the WBO instance F = (FH , ⋃li=1 FSi).

Proposition 3 implies that Pareto-MCS enumeration of a MOWBO instance W = (FH,OS) can be reduced to enumerating MCSs of the WBO instance F = (FH, ⋃FS∈OS FS) as follows: (1) build F fromW; (2) enumerate MCSs C of F using an off-the-shelf MCS enumerator and convert them to Multi-MCSs C = (C1,C2, . . . ,Cl) of W, where Ci = {(c, ω) : (c, ω) ∈ C∩FSi} for all 1 ≤ i ≤ l; (3) filter out Multi-MCSs dominated by any other Multi-MCS using non dominated sorting [Deb et al., 2000]. Therefore, efficient state-of-the-art algorithms for MCS enumeration can be used to enumerate Pareto-MCSs right off-the-shelf.

4 Experimental Results

This section evaluates the performance of the Pareto-MCS based approach on instances of the Virtual Machine Consolidation (VMC) problem. We refer to our approach for enumerating Pareto-MCSs as PCLD, since the CLD [Marques-Silva et al., 2013] algorithm was used to compute MCSs. The performance of PCLD is compared with that of the state-of-theart evolutionary algorithms for VMC. PCLD was built on top of Sat4j-PB [Le Berre and Parrain, 2010] (version 2.3.4), and the evolutionary algorithms were implemented on top of the MOEA Framework 1 (version 2.9.1).

In VMC, we have several servers with fixed resource capacities and Virtual Machines (VMs) with requirements of those same resources. Each VM must be placed in some server, but server capacities cannot be exceeded and some VMs cannot be placed in the same server. There exists an initial placement, i.e., a VM can be associated with an initial server, incurring a migration cost if the VM is placed in a different one. A migration budget constraint can be used to enforce an upper limit on the migration costs, and is specified as a percentile bp of the total memory capacity of the servers. The goal is to find a placement for all VMs that satisfies the constraints and simultaneously minimizes (1) energy consumption of servers, (2) migration costs and (3) resource wastage. The latter is a measure of the imbalance of server resource usage. A detailed description of the VMC problem can be found in the literature [Terra-Neves et al., 2017; Zheng et al., 2016]. The evaluation is performed on publicly available benchmarks 2 , based on subsets of workload traces randomly selected from the Google Cluster Data project 3 .

In the VMC problem instances, it is impractical to find the full set of Pareto-optimal solutions within a reasonable amount of time. Therefore, the evaluation process considers approximations of the Pareto-optimal solution set that each algorithm is able to produce within the time limit of 1800 seconds. The Hypervolume (HV) quality indicator [Zitzler and Thiele, 1999] provides a combined measure of convergence and diversity. Larger values of HV mean that the solution set is composed of solutions of better quality and/or diversity. The Inverted Generational Distance (IGD) indicator [Zhang and Li, 2007] measures the average Euclidean distance, in the cost space, between the Pareto optimal solutions and the approximation returned by the algorithm, and a smaller value is preferred. Since the Pareto front is unknown, we use instead the combination of the solutions produced by all algorithms evaluated. The evaluation was conducted on an AMD Opteron 6376 (2.3 GHz) running Debian jessie and each algorithm was executed with a memory limit of 4 GB. Evolutionary algorithms were executed with 10 different seeds for each instance, and the analysis is performed using the median values over all executions.

1 http://moeaframework.org/

2 http://sat.inesc-id.pt/dome/

3 http://code.google.com/p/googleclusterdata/

Figure 4: IGD distributions (bp = 5%).

Figure 6: IGD distributions (bp = 1%).

The performance of PCLD is compared with that of the evolutionary algorithms VMPMBBO [Zheng et al., 2016], MGGA [Xu and Fortes, 2010] and NSGAII [Deb et al., 2000]. MGGA was adapted to consider migration costs instead of thermal dissipation and configured as suggested by Xu and Fortes [2010]. We note that VMPMBBO was originally designed for optimizing energy consumption and resource wastage and was run with the configuration suggested by Zheng et al. [2016]. The only difference is that we use 2 additional subsystems to account for migration costs. NSGAII is a general purpose genetic algorithm and was fine tuned to solve the VMC problem.

Figures 1 and 2 show the HV and IGD distributions, respectively, for all algorithms when bp = 100%. A point (x, y) in the HV (IGD) distribution plot indicates that the given approach obtained an HV (IGD) equal to or greater (lower) than y for x instances. We can see that NSGAII has the best performance both in terms of HV and IGD, being able to find solution sets for more instances and of better quality. However, considering large migration costs is not realistic for an active data center where live migrations may result in a large performance deterioration of running applications. Therefore, considering a limited budget for migrations of VMs is more realistic. With migration budgets of 5% and 1%, the performance of the evolutionary algorithms degrades considerably, while PCLD remains robust, as we can see in figures 3, 4, 5 and 6. MGGA's performance degrades the most, since it is unable to find many feasible solutions. In fact, with bp = 1%, MGGA fails to find feasible solutions for any instance. Moreover, PCLD is able to find feasible solutions for far more instances than the remaining algorithms.

5 Conclusion

This paper introduces the Pareto Minimal Correction Subset (Pareto-MCS) of a multi-objective constrained optimization problem. An equivalence relationship between Pareto-MCSs and Pareto-optimal solutions shows that Pareto-optimal solution enumeration can be reduced to Pareto-MCS enumeration. Additionally, we show that Pareto-MCS enumeration can be reduced to MCS enumeration, allowing the usage of off-the-shelf MCS enumeration algorithms, instead of developing entirely new algorithms for Pareto-MCS enumeration.

An experimental evaluation on instances of the Virtual Machine Consolidation (VMC) problem shows that Pareto-MCS enumeration is competitive with the state-of-the-art on a large set of problem instances. Not only is this new approach able to find solutions for more instances, but it is also able to find solution sets of higher quality in more constrained instances.

Acknowledgments

This work was supported by national funds through FCT with references UID/CEC/50021/2013, SFRH/BD/111471/2015 and CMU/AIR/0022/2017.