---
title: "Integrating Pseudo-Boolean Constraint Reasoning in Multi-Objective Evolutionary Algorithms"
authors:
  - "Miguel Terra-Neves"
  - "Inês Lynce"
  - "Vasco Manquinho"
doi: "10.24963/ijcai.2019/165"
url: "https://ijcai.org/proceedings/2019/165"
pdf: "https://ijcai.org/proceedings/2019/0165.pdf"
venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence"
year: 2019
pages: "1184-1190"
track: "Main track"
keywords:
  - "Constraints and SAT: SAT: Evaluation and Analysis"
  - "Constraints and SAT: SAT: Solvers and Tools"
  - "Constraints and SAT: Constraints: Evaluation and Analysis"
  - "Constraints and SAT: Constraints: Solvers and Tools"
  - "Heuristic Search and Game Playing: Combinatorial Search and Optimisation"
---

# Integrating Pseudo-Boolean Constraint Reasoning in Multi-Objective Evolutionary Algorithms

Miguel Terra-Neves, Inês Lynce, Vasco Manquinho

*Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 1184-1190. DOI: [10.24963/ijcai.2019/165](https://doi.org/10.24963/ijcai.2019/165)

## Abstract

Constraint-based reasoning methods thrive in solving problem instances with a tight solution space. On the other hand, evolutionary algorithms are usually effective when it is not hard to satisfy the problem constraints. This dichotomy has been observed in many optimization problems. In the particular case of Multi-Objective Combinatorial Optimization (MOCO), new recently proposed constraint-based algorithms have been shown to outperform more established evolutionary approaches when a given problem instance is hard to satisfy. In this paper, we propose the integration of constraint-based procedures in evolutionary algorithms for solving MOCO. First, a new core-based smart mutation operator is applied to individuals that do not satisfy all problem constraints. Additionally, a new smart improvement operator based on Minimal Correction Subsets is used to improve the quality of the population. Experimental results clearly show that the integration of these operators greatly improves multi-objective evolutionary algorithms MOEA/D and NSGAII. Moreover, even on problem instances with a tight solution space, the newly proposed algorithms outperform the state-of-the-art constraint-based approaches for MOCO.

## Full text

## 1 Introduction

In several real-world problems (e.g. software product lines [Henard et al., 2015] or virtual machine consolidation in data centers [Zheng et al., 2016]), there are several conflicting objectives to be optimized such that a set of Boolean linear constraints must be satisfied. These Multi-Objective Combinatorial Optimization (MOCO) problems have multiple optimal solutions, known as Pareto optimal solutions, each of them favoring certain objectives at the expense of others. The enumeration of all Pareto optimal solutions is known to be very hard. In practice, most algorithms can only approximate the Pareto front, i.e. the set of all Pareto optimal solutions.

Multi-Objective Evolutionary Algorithms (MOEAs) have been at the forefront for solving MOCO problems [Deb et al., 2000; Zhang and Li, 2007; Zheng et al., 2016]. However, in problem instances where it is hard to satisfy all problem constraints, the performance of MOEAs starts to decline. On the other hand, recently proposed constraint-based methods [Soh et al., 2017; Terra-Neves et al., 2018] thrive in solving tightly constrained instances. This duality, between evolutionary algorithms and constraint-based methods, motivated the selective integration of constraint solving in MOEAs [Henard et al., 2015; Xiang et al., 2018].

In previous works, MOEA tools use a constraint solver for correcting individuals or adding diversity to the population. An individual corresponds to a complete assignment to all problem variables. Given a complete assignment that does not satisfy all problem constraints, a partial assignment can be generated by unassigning the variables in unsatisfied constraints, while the remaining variables are fixed. Next, a constraint solver is used to extend the partial assignment into a complete satisfying assignment. As a result, a new feasible individual is added to the population. However, in general, there is no guarantee that the partial assignment can be extended to satisfy all problem constraints. In this paper, we propose a core-based approach to solve this issue.

The main contributions of the paper are: (1) a new corebased smart mutation operator that corrects individuals in any MOEA for MOCO; (2) a novel smart improvement operator based on Minimal Correction Subsets (MCSs); (3) the usage of incremental solving to avoid the constraint solver from generating the same individual; and (4) an extensive experimental evaluation showing that MOEA solvers with the proposed operators can outperform both the classic MOEA tools and recently proposed constraint-based solvers for MOCO.

The paper is organized as follows. Section 2 defines MOCO and MCS, and briefly reviews MOEAs and the virtual machine consolidation problem. Next, Section 3 describes the new core-based smart mutation operator, while Section 4 proposes the usage of smart improvements using MCSs. Section 5 presents an extensive experimental evaluation of the proposed techniques and the paper concludes in Section 6.

## 2 Preliminaries

This section starts by describing MOCO and MOEAs. Next, MCS based approaches for MOCO solving are introduced. Finally, we describe Virtual Machine Consolidation (VMC), a multi-objective benchmark problem used to evaluate the smart evolutionary operators proposed in this paper.

## 2.1 Multi-Objective Combinatorial Optimization

Let X = {x1, . . . , xn} be a set of n Boolean variables. A literal is either a variable xi or its complement xi. Given a set of m literals l1, . . . , lm and respective coefficients ω1, . . . , ωm ∈ N, a Pseudo-Boolean (PB) expression is a weighted sum of literals ∑mi=1 ωi ·li. Given an integer k ∈ N, a linear PB constraint has the form:

<!-- formula-not-decoded -->

Note that a clause (l1 ∨ · · · ∨ lm) is equivalent to the PB constraint (∑mi=1 li ≥ 1). In some cases, we use clause notation for ease of explanation.

Given a set φ = {c1, . . . , cm} of m PB constraints, the Pseudo-Boolean Satisfiability (PBS) problem consists of deciding if there exists a complete assignment α : X → {0, 1} that satisfies all constraints in φ. If that is the case, we say that φ is satisfiable and α is a model of φ, denoted α(φ) = 1. If α does not satisfy φ, we say that α is unfeasible, denoted α(φ) = 0. If φ is unsatisfiable, then α(φ) = 0 for any assignment α. An instance of the Pseudo-Boolean Optimization (PBO) problem [Boros and Hammer, 2002] is a pair Φ = (φ, f(X)), where φ = {c1, . . . , cm} is a set of m PB constraints and f(X) is a PB expression representing a cost function. The goal is to find a model α of φ that minimizes its cost, denoted as f(α).

Example 2.1 Let (φ, f(X)) denote a PBO instance where φ = {x1 + x2 + x3 ≥ 2, x1 + x2 = 1} and f(X) = x1 + 2x2 + 3x3. In this case, an optimal solution would be α = {(x1, 1), (x2, 0), (x3, 1)} with an overall cost of 4.

In this work, we consider that a MOCO [Ulungu and Teghem, 1994] instance is a pair Φ = (φ, F(X)), where φ is a set of PB constraints to satisfy and F(X) = (f1(X), . . . , fk(X)) is a vector of k PB expressions to minimize, defined over a set X of Boolean variables. Given a complete assignment α such that α(φ) = 1, its cost vector is defined as F(α) = (f1(α), . . . , fk(α)). Let α and α′ be two distinct complete assignments such that α(φ) = α′ (φ) = 1. We say that F(α) dominates F(α′ ) (α dominates α′ ), denoted F(α) ≺ F(α′ ) (α ≺ α′ ), if and only if fi(α) ≤ fi(α′ ) for all i = 1..k and fj(α) &lt; fj(α′ ) for some j = 1..k. The Pareto front PΦ of Φ is the set of its nondominated cost vectors, i.e., F(α) ∈ PΦ if and only if α(φ) = 1 and no α′ exists such that α′ (φ) = 1 and F(α′ ) ≺ F(α). α is said to be a Pareto-optimal solution of Φ if and only if F(α) ∈ PΦ. In MOCO, the goal is to find the Pareto front of Φ.

Example 2.2 Let (φ, F (X)) denote a MOCO instance where φ = {x1 + x2 + x3 ≥ 2} and F(X) = (f1(X), f2(X)) = (2x1 + x2, 2x2 + 2x3). In this case, there are two Pareto optimal solutions: α1 = {(x1, 0), (x2, 1), (x3, 1)} with costs (1, 2) and α2 = {(x1, 1), (x2, 1), (x3, 0)} with costs (3, 0). Note that α1 provides a better value for f1, while α2 is able to improve on f2. All other satisfiable assignments to φ are dominated by either α1 or α2.

For most problems, it is not possible to enumerate all Pareto optimal solutions PΦ in a reasonable amount of time. Therefore, we focus on finding a set of solutions that best approximates the Pareto front PΦ within a given time limit.

## Algorithm 1 Typical MOEA framework for MOCO

Input: Φ = (φ, F (X))

- 1: P ←InitialSolutions(Φ)
- 2: while stopping criteria not triggered do
- 3: Q←GenerateOffsprings(P)
- 4: P ←SelectSurvivors(P,Q)
- 5: end while
- 6: return FilterDominated(P)

## 2.2 Multi-Objective Evolutionary Algorithms

The typical MOEA framework is presented in Algorithm 1. Such algorithms maintain a fixed size population P of complete assignments, referred to as individuals. At each iteration, referred to as a generation, a set Q of |P| offsprings is generated by applying crossover and mutation operators to selected individuals in P (line 3). Then, |P| individuals among P and Q are selected to become the population in next generation (line 4). This process is repeated until some stopping criteria is met (e.g. number of generations, time limit, etc).

The crossover operator produces a new offspring α from two individuals α1 and α2 by mixing their variable assignments. For example, given some variable x ∈ X, uniform crossover [Spears and De Jong, 1995; Syswerda, 1989] has a fixed probability (typically 0.5) of setting α(x) = α1(x), otherwise it sets α(x) = α2(x). Note that crossover is applied with a given probability pcr, referred to as crossover rate, and therefore, with probability 1 - pcr, α is a clone of either α1 or α2 instead. The mutation operator produces an offspring α′ by applying perturbations (e.g. flipping the values of some variables) to an individual α. Similarly to crossover, the frequency of mutation is also controlled by a configurable mutation rate pmr. Note that crossover and mutation may produce unfeasible individuals. In this work, the three feasibility rules of Deb [2000] are employed to handle constraints in MOEAs: (1) if two individuals are feasible, the best one is chosen; (2) if one individual is feasible and the other is not, the feasible one is chosen; (3) if two individuals are infeasible, the one with the smallest degree of constraint violation is chosen.

MOEAs employ a ranking scheme to define probabilities for individuals to participate in crossover/mutation and decide which individuals survive to the next generation. Typically, the ranking scheme is the main distinguishing factor between MOEAs, while the crossover/mutation operators remain the same. A good ranking scheme should promote fast convergence and ensure that the final population is well distributed. For example, NSGAII [Deb et al., 2000] is a popular genetic algorithm that favors nondominated individuals with cost vectors in less crowded areas of the cost space. In MOEA/D [Zhang and Li, 2007], each individual is assigned a scalarized single-objective version of the multi-objective problem. An individual is replaced by offsprings with smaller costs in regard to its scalarized problem.

## 2.3 Unsatisfiable Cores andMinimal Correction Subsets

Let φ be an unsatisfiable set of PB constraints. A subset φC ⊆ φ is an unsatisfiable core of φ if and only if φC is also unsatisfiable.

Let φH and φS be sets of hard and soft PB constraints, respectively, such that φH is satisfiable and φH ∪φS is unsatisfiable. Note that all hard constraints must be satisfied. On the other hand, soft constraints are not required to be satisfied, but the goal is to satisfy as many as possible. A subset C ⊆ φS is an MCS if and only if φH ∪ (φS \ C) is satisfiable and φH ∪ (φS \ C) ∪ {c} is unsatisfiable for all c ∈ C.

Example 2.3 Let φH = {x1+x2+x3 ≥ 2, x1+x2 = 1} be the set of hard constraints and φS = {x1 = 0, x2 = 0, x3 = 0} the set of soft constraints. In this case, we have two MCS: C1 = {x1 = 0, x3 = 0} and C2 = {x2 = 0, x3 = 0}.

Several techniques exist in the literature for computing unsatisfiable cores [Goldberg and Novikov, 2003; Dershowitz et al., 2006] and MCSs [Bailey and Stuckey, 2005; Felfernig et al., 2012; Marques-Silva et al., 2013; Menc´ıa et al., 2015]. MCSs can be used to find approximate solutions of PBO instances as follows. Let Φ = (φ, f(X)) be a PBO instance, where f(X) = ∑mi=1 ωi · li. Let Lf = ⋃mi=1 {(li)} denote the set of clauses built from the negation of the literals that appear in f(X). We set φH = φ and φS = Lf and obtain an MCS C through the application of an MCS algorithm. We abuse notation and use f(C) to denote the cost of C, defined as follows: f(C) = ∑(li)∈C ωi.

Observe that any complete assignment α that satisfies φ ∪ (Lf \ C) will have cost f(α) = f(C), which provides an approximation of the optimal cost for Φ. Actually, any PBO instance can be reduced to finding the MCS C ⊆ Lf with minimum value of f(C) [Birnbaum and Lozinskii, 2003].

Recently, it was shown that MCSs can also be used to find the Pareto front of MOCO instances. Let Φ = (φ, F(X)) be a MOCO instance with F(X) = (f1(X), . . . , fk(X)), and LF = ⋃ki=1 Lfi . Terra-Neves et al. [2017] proved that one can find PΦ by setting φH = φ and using an MCS algorithm to enumerate the MCSs of LF .

Example 2.4 The MOCO instance (φ, (f1(X), f2(X))) from example 2.2 can be solved through MCS-enumeration as follows. Let φH = φ and let Lf1 = {x1, x2} and Lf2 = {x2, x3} derived from f1(X) and f2(X) as described. Consider LF = Lf1 ∪ Lf2 the set of soft constraints. Next, enumerate the MCSs of (φH,LF ). In this case, the MCSs corresponding to the Pareto frontier would be C1 = {x1, x2} and C2 = {x2, x3}. C3 = {x1, x2, x3} is also an MCS, but its solution is dominated by the solution of C1.

## 2.4 Virtual Machine Consolidation

In this section the Virtual Machine Consolidation (VMC) problem is introduced, since it will be used in Sections 3 and 4 for a better understanding of the new operators. Moreover, VMC instances will also be used to evaluate the performance of the operators proposed in this work. VMC is a well known resource allocation problem that arises in the context of a cloud provider, where a set of running Virtual Machines (VMs) must be allocated to the servers in a data center. All VMs must be placed in some server, while minimizing energy consumption, resource wastage and VM migration costs.

The VM placement is subject to the following constraints: (1) each VMmust be placed in exactly one server; (2) the total resource requirements (e.g. CPU, memory, etc) of the VMs placed in some server cannot exceed its resource capacities; (3) some VMs belong to the same job and must be placed in different servers in order to achieve higher levels of fault tolerance; and (4) the VM migration costs cannot exceed a given fixed migration budget enforced by the cloud provider. In this paper, we focus solely on VM placement variable encodings. The interested reader is referred to the literature for further details on the mathematical formulation of the VMC problem's constraints and objectives [Zheng et al., 2016; Terra-Neves et al., 2017].

Consider a set V = {v1, . . . , vm} of m VMs and a set S = {s1, . . . , sn} of n servers. An integer variable xIi is introduced for each VM vi ∈ V , with domain {1, . . . , n}. The value of xIi indicates the server that accommodates vi, i.e., xIi = j means that vi is placed in sj. We consider this encoding for the individuals in a MOEA's population. Hence, the crossover of two individuals α1 and α2 produces a new individual α12 with approximately half of the VMs placed as in α1 and the remaining ones as in α2. The mutation of α12 corresponds to picking a VM v at random and choosing a random server to accommodate v.

However, the smart operators proposed in this paper require all variables to be Boolean. For each VM-server pair vi ∈ V and sj ∈ S, we introduce a Boolean variable xBi,j that indicates whether vi is placed in server sj. Therefore, if xIi = j, we have xBi,j = 1 and xBi,k = 0 for all k ̸= j and vice-versa. A different encoding is used in the evolutionary algorithm because the integer encoding naturally captures the constraint that each VMmust be placed in exactly one server, improving the performance of the evolutionary process. Ideally, the MOEA should also operate on the Boolean encoding in order to better generalize to other kinds of MOCO problems, but the purpose of this paper is to highlight the benefits of combining MOEAs with logic-based methods, and thus we leave its generalization for future work.

## 3 Smart Mutation

Smart mutation is the process of using a constraint solver to turn an unfeasible individual of a MOEA's population into a feasible one. Given an unfeasible individual, smart mutation finds a set of variable assignments that are not responsible for constraint violations, enforces those assignments, and uses a constraint solver to assign the remaining variables, thus producing a feasible individual.

Smart mutation was recently proposed by Henard et al. [2015] in the context of Software Product Line Configuration (SPLC). The constraints of an SPLC instance can be expressed as a set of clauses, and thus the authors proposed the SATIBEA algorithm, which uses a Boolean satisfiability solver within IBEA [Zitzler and K¨unzli, 2004] to correct unfeasible individuals. Given such an individual, SATIBEA considers the assignments of variables appearing in unsatisfied clauses to be the ones responsible for constraint violations. Although this rule suffices for the SPLC problem, it does not generalize to other applications, specially when

## Algorithm 2 Generalized smart mutation

## Input: φ, α

- 1: XA ←InitAssigned(φ, α)
- 2: φA ← ⋃x∈XA,α(x)=1 {(x)} ∪ ⋃x∈XA,α(x)=0 {(x)}
- 3: while not SAT(φ ∪ φA) do
- 4: φC ←UnsatCore(φ ∪ φA)
- 5: φA ←φA \ (φC ∩ φA)
- 6: end while
- 7: αfeasible ←Model(φ ∪ φA)
- 8: return αfeasible

more general types of constraints are involved, such as PB constraints. Hence, in general, SATIBEA's smart mutation operator is not guaranteed to produce a feasible individual.

We propose a generalized smart mutation operator that, given a set of constraints φ and an individual α, it uses unsatisfiable cores to determine which variable assignments in α are responsible for constraint violations. Its pseudo-code is presented in Algorithm 2. It starts by initializing a set XA of variables that are believed to not be responsible for α's constraint violations (line 1). Then, a set φA is built with clauses enforcing the partial assignment that results from restricting α to the variables in XA (line 2). A PBS oracle is used to check if φ ∪ φA is satisfiable (line 3), in which case a model of φ ∪ φA is returned as the new individual (line 7). Otherwise, a core of φ ∪ φA is extracted (line 4) and the clauses of φA present in the core are removed from φA (line 5). This process is repeated until φ ∪ φA becomes satisfiable.

In line 1, XA can be initialized with all problem variables and let generalized smart mutation itself determine the variables responsible for constraint violations using unsatisfiable cores. However, one may speed-up the process by exploiting domain knowledge to initialize XA. For VMC, we unassign the following variables: (1) all variables of VMs placed in servers with overloaded resource capacities; (2) all variables of VMs of the same job placed in the same server; (3) all variables of migrated VMs if the migration budget is exceeded.

Given a model α, we prevent smart mutation from producing α again in the future by adding the clause (∨x∈X,α(x)=1 x∨∨x∈X,α(x)=0 x) to φ. As a result, our smart mutation operator works in an incremental way and adds diversity to the population by ensuring to always produce a different individual. Although very unlikely, if the smart mutation operator produces a core φC such that φC ∩ φA = ∅, then we know that the whole feasible search space has been explored and the MOEA can be terminated.

Note that PBS is an NP-Hard problem [Roussel and Manquinho, 2009]. Therefore, smart mutation should be executed sparingly. Otherwise, most of the time will be spent on the PBS oracle instead of evolving the population. The frequency of smart mutation is controlled through a configurable smart mutation rate psmr. Additionally, in order to prevent smart mutation from wasting unreasonable amounts of time on hard PBS instances, one may impose a configurable conflict 1 budget bsm on each run of smart mutation. If the oracle exhausts

1 Modern PB solvers apply an adaptation of the conflict-driven DPLL procedure used in state-of-the-art Boolean satisfiability

## Algorithm 3 Smart improvement

## Input: φ, LF , α

- 1: XA ←InitAssigned(φ, LF , α)
- 2: φA ← ⋃x∈XA,α(x)=1 {(x)} ∪ ⋃x∈XA,α(x)=0 {(x)}
- 3: C ←MCS(φ ∪ φA,LF )
- 4: αimproved ←Model(φ ∪ φA ∪ (LF \ C))
- 5: return αimproved

that budget, smart mutation is interrupted and the original unfeasible individual is returned instead.

## 4 Smart Improvement

We propose a novel smart improvement operator, inspired on MCS-based algorithms for enumerating the Pareto front of MOCO instances [Terra-Neves et al., 2017]. Given a feasible individual α, smart improvement uses an MCS oracle to produce a similar offspring α′ . This process is outlined in Algorithm 3. First, similarly to smart mutation, we build a set φA of clauses enforcing a subset of α's variable assignments (lines 1 and 2). In VMC, this step corresponds to selecting a subset of VMs to relocate and enforcing the variables of the remaining VMs. We select relocating VMs randomly with probability given by a configurable relaxation rate prr. Then, an MCS oracle is invoked with φH = φ ∪ φA and φS = LF , producing an MCS C (line 3). Finally, the improved offspring is a model of φ ∪ φA ∪ (LF \ C) (line 4). Similarly to smart mutation, the clause (∨(l)∈C l) is added to φ to prevent smart improvement from producing C again in the future.

Observe that φH = φ ∪ φA is defined as the set of hard constraints given to the MCS algorithm. In our incremental implementation, a new blocking clause is added to φ whenever a new solution is found in the smart mutation operator, or when a new MCS is generated. As a result, there is no guarantee that φH is satisfiable. In those situations, no new offspring is generated. Note also that finding an MCS is NPHard. Hence, as in smart mutation, a conflict budget bsi is imposed on each smart improvement run.

Any MCS algorithm can be used in the smart improvement operator. In this work, MCSs are computed using the Stratified CLD (SCLD) algorithm for MOCO proposed by TerraNeves et al. [2018]. SCLD first splits the literals in LF into a sequence of partitions P1 . . . Pk. The partitioning is such that the literals in the first few partitions are the ones with the highest impact on the cost function values. Then, for each partition Pi, SCLD sets φH = φ ∪ φA ∪ ⋃i-1 j=1 (Pj \ Cj) and φS = Pi, where Cj is the MCS computed at iteration j, and uses CLD to compute Ci. In the end, C = ⋃kj=1 Cj is an MCS for φH = φ ∪ φA and φS = LF .

## 5 Experimental Results

This section evaluates the performance of the smart operators proposed in Sections 3 and 4 on instances of the VMC problem. We consider the benchmark set publicly available

solvers [Roussel and Manquinho, 2009].

on the DOME project website 2 . The smart operators were implemented in the VMAlloc solver 3 , a collection of algorithms for solving instances of the VMC problem which includes implementations of MOEA/D [Zhang and Li, 2007], NSGAII [Deb et al., 2000] and SCLD. PBS instances were solved using Sat4j [Le Berre and Parrain, 2010] 4 . We evaluate the impact of the smart operators on the performance of NSGAII and MOEA/D, and make a comparison with SCLD as well. All algorithms were configured as suggested in the literature [Terra-Neves et al., 2017; Terra-Neves et al., 2018]. Smart mutation was applied to each offspring produced by the regular genetic operators with probability psmr = 0.01. If the offspring was already feasible, smart improvement was used instead with relaxation rate prr = 0.2. Conflict budgets were set as follows: bsm = 20000 and bsi = 500000.

The quality of the Pareto front approximations was evaluated using the Inverted Generational Distance (IGD) [Coello Coello and Sierra, 2004] and Hypervolume (HV) [Zitzler, 1999] performance metrics. IGD is a combined measure of convergence and diversity. Given some approximation P, IGD measures the average Euclidean distance from the cost vectors in some reference front PR (ideally the Pareto front if known) to the closest vector in P. Smaller values of IGD indicate that the approximation is composed of solutions of higher quality in terms of convergence and/or diversity. We combined the approximations produced by all algorithms evaluated in this section to build the reference fronts for each VMC instance. HV is another combined metric that measures the volume of the cost space dominated by the approximation P, up to a given reference point, and thus larger values are preferred. All cost vectors in P and PR are normalized before computing IGD and HV. The reference point coordinates for HV are set to 1+ 1 |PR| .

We consider one additional metric, based on the primal integral used in the evaluation of mixed integer programming heuristics [Berthold, 2013], referred to as Unfeasible Integral (UI). Let u(t) denote the number of unfeasible solutions in the population observed at instant t during the execution of some MOEA. Assuming a time limit of T seconds, the UI is the integral of u(t), in interval [0, T], divided by T. Smaller values of UI indicate that the algorithmmaintains a larger average count of feasible individuals in the population throughout its execution. Observe that, in order to perform a fair comparison, UI should only be considered if the population size is the same for all algorithms (100 in this evaluation).

Each algorithm was executed 10 times with different seeds for each instance, and the analysis is performed using the median values over all executions. Statistical tests were performed with confidence intervals of 95% in order to assess the significance of the results. These were successful for at least 60% of all instances for all algorithm pairs. Memory and time limits of 4 GB and 1800 seconds respectively were used. The evaluation was conducted on an AMD Opteron 6376 (2.3 GHz) with 128 GB of RAM, running Debian jessie.

Figures 1 to 9 show the median UI, IGD and HV distributions obtained with each algorithm for VMC instances with migration budgets equal to 100%, 5% and 1% of the data centers total memory capacity. We refer to NSGAII (MOEA/D) with smart mutation enabled as NSGAII-SM (MOEA/D-SM). NSGAII-SI (MOEA/D-SI) corresponds to NSGAII (MOEA/D) with smart mutation plus improvement. A point (x, y) in an UI/IGD (HV) distribution plot indicates that the given algorithm obtained an UI/IGD (HV) equal to or lower (greater) than y for x instances. For example, the point (100, 81) on MOEA/D-SM's line in Figure 1 indicates that MOEA/D-SM obtained UIs equal to or smaller than 81 for 100 instances. In order to improve the readability of Figures 4 to 6, we only display IGD values up to 1.2.

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

3 https://github.com/MiguelTerraNeves/VMAlloc

4 https://gitlab.ow2.org/sat4j/sat4j (27 Jan. 2019)

## 5.1 Impact of Smart Mutation

Figures 2 and 3 show that, in the 5% and 1% migration budget instances, smart mutation significantly improves the number of feasible solutions in the population for both MOEA/D and NSGAII. Moreover, we have also observed a faster convergence when smart mutation is used, since feasible individuals are found in earlier iterations of MOEA/D and NSGAII. Because the constraints of the 100% instances are easier to satisfy, we observe a lack of improvement in Figure 1. MOEA/D and NSGAII are already able to find many feasible solutions for the 100% instances without smart mutation, and smart operators are significantly slower than typical genetic operators. Nonetheless, NSGAII-SM is able to find feasible solutions for all 300 100% instances, 28 (64) more than NSGAII (MOEA/D). MOEA/D-SM does so for 297 of those instances.

In Figures 5, 6, 8 and 9, we can see a significant improvement in terms of IGD and HV for both NSGAII-SM and MOEA/D-SM for the 5% and 1% instances. Therefore, by injecting the population with feasible solutions, smart mutation enables the MOEAs to find high quality Pareto front approximations and even outperform SCLD, the state-of-the-art for such instances. Figures 4 and 7 show that smart mutation barely impacts the performance of MOEA/D in the 100% instances. However, we see some performance degradation for NSGAII. We can conclude that smart mutation improves the performance of MOEAs in tightly constrained problems, at the expense of some performance in loosely constrained ones.

## 5.2 Impact of Smart Improvement

Figures 1 to 3 show a degradation in terms of UI when smart improvement is enabled. This is expected since smart improvement is much more expensive than smart mutation, and thus less time is spent searching for feasible solutions. Nonetheless, the number of instances for which at least one feasible solution is found is similar with and without smart improvement. Moreover, Figures 4 to 9 show a considerable improvement for both MOEA/D-SI and NSGAII-SI in terms of approximation quality, particularly in HV. Not only does smart improvement enhances the performance in tightly constrained instances, it compensates for the performance degradation observed in loosely constrained ones for NSGAII.

## 6 Conclusion and FutureWork

Recently, constraint-based methods for MOCO have been shown to outperform state-of-the-art evolutionary algorithms, such as NSGAII and MOEA/D, when the problem's constraints are hard to satisfy [Terra-Neves et al., 2018]. Following previous work on using constraint solvers in MOEAs [Henard et al., 2015; Xiang et al., 2018], we propose a generalized smart mutation operator for correcting unfeasible individuals, and a smart improvement operator that uses MCSs to improve already feasible individuals. Experimental results in a large set of VMC instances show that the combination of evolution and constraint solving significantly outperforms pure evolutionary and constraint-based approaches.

Figure 1: UI distributions (100%).

![Image](https://ijcai.org/proceedings/2019/fulltext/165/image_000000_5840e3c64b8cf63e99214635278d2451cccfa082aad122b39e24bdd82dfe4257.png)

Figure 2: UI distributions (5%).

Figure 3: UI distributions (1%).

![Image](https://ijcai.org/proceedings/2019/fulltext/165/image_000001_2995d0367a75aa4a60e11ddc9086c3a9cdbc2d4a1dc46538ebccb1709c10e977.png)

Figure 4: IGD distributions (100%).

Figure 5: IGD distributions (5%).

Figure 6: IGD distributions (1%).

![Image](https://ijcai.org/proceedings/2019/fulltext/165/image_000002_89b40243154a5fa1d482fae4f9167804e7611cf40373a1271f6af546c395db25.png)

Figure 7: HV distributions (100%).

Figure 8: HV distributions (5%).

Figure 9: HV distributions (1%).

Recall that, currently, an integer encoding for individuals is used that is more suitable for VMC than a Boolean encoding. As future work, we propose to evaluate the performance of the Boolean encoding and investigate possible new encodings suitable for Boolean MOCOs. Moreover, general heuristics should be developed for the assigned variable initialization step of the smart mutation and improvement procedures. One should also explore deeper integration between MOEAs and constraint solvers (e.g. exploiting the scalarization weights when applying smart improvement within MOEA/D). Lastly, the performance of these techniques should be evaluated on other MOCO benchmarks besides VMC, such as SPLC.

## Acknowledgments

This work was supported by national funds through FCT with references UID/CEC/50021/2019, SFRH/BD/111471/2015, PTDC/CCI-COM/31198/2017 and DSAIPA/AI/0044/2018.

## References

1. [Bailey and Stuckey, 2005] J. Bailey and P. Stuckey. Discov- ery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization. In Symposium on Practical As- pects of Declarative Languages, pages 174-186, 2005.
2. [Berthold, 2013] T. Berthold. Measuring the Impact of Pri- mal Heuristics. Operations Research Letters, 41(6):611- 614, 2013.
3. [Birnbaum and Lozinskii, 2003] E. Birnbaum and E. Lozin- skii. Consistent Subsets of Inconsistent Systems: Structure and Behaviour. Journal of Experimental & Theoretical Ar- tificial Intelligence, 15(1):25-46, 2003.
4. [Boros and Hammer, 2002] E. Boros and P. L. Hammer. Pseudo-Boolean Optimization. Discrete Applied Mathe- matics, 123(1):155-225, 2002.
5. [Coello Coello and Sierra, 2004] C. A. Coello Coello and M. R. Sierra. A Study of the Parallelization of a Coevolu- tionary Multi-objective Evolutionary Algorithm. In Mex- ican International Conference on Artificial Intelligence, pages 688-697, 2004.
6. [Deb et al., 2000] K. Deb, S. Agrawal, A. Pratap, and T. Me- yarivan. A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimisation: NSGA-II. In International Conference on Parallel Problem Solving from Nature, pages 849-858. Springer, 2000.
7. [Deb, 2000] K. Deb. An Efficient Constraint Handling Method for Genetic Algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2-4):311-338, 2000.
8. [Dershowitz et al., 2006] N. Dershowitz, Z. Hanna, and A. Nadel. A Scalable Algorithm for Minimal Unsatisfi- able Core Extraction. In International Conference on The- ory and Applications of Satisfiability Testing, pages 36-41, 2006.
9. [Felfernig et al., 2012] A. Felfernig, M. Schubert, and C. Ze- hentner. An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets. Artificial Intelligence for Engineering De- sign, Analysis and Manufacturing, 26(1):53-62, 2012.
10. [Goldberg and Novikov, 2003] E. Goldberg and Y. Novikov. Verification of Proofs of Unsatisfiability for CNF Formu- las. In Conference on Design, Automation and Test in Eu- rope, pages 10886-10891, 2003.
11. [Henard et al., 2015] C. Henard, M. Papadakis, M. Harman, and Y. Le Traon. Combining Multi-Objective Search and Constraint Solving for Configuring Large Software Prod- uct Lines. In International Conference on Software Engi- neering, pages 517-528, 2015.
12. [Le Berre and Parrain, 2010] D. Le Berre and A. Parrain. The Sat4j Library, Release 2.2. Journal on Satisfiability, Boolean Modeling and Computation, 7(2-3):59-6, 2010.
13. [Marques-Silva et al., 2013] J. Marques-Silva, F. Heras, M. Janota, A. Previti, and A. Belov. On Computing Mini- mal Correction Subsets. In International Joint Conference on Artificial Intelligence, pages 615-622, 2013.
14. [Mencía et al., 2015] C. Mencía, A. Previti, and J. Marques- Silva. Literal-Based MCS Extraction. In International Joint Conference on Artificial Intelligence, pages 1973- 1979, 2015.
15. [Roussel and Manquinho, 2009] O. Roussel and V. Man- quinho. Pseudo-Boolean and Cardinality Constraints. In Handbook of Satisfiability, pages 695-733. 2009.
16. [Soh et al., 2017] T. Soh, M. Banbara, N. Tamura, and D. Le Berre. Solving Multiobjective Discrete Optimization Problems with Propositional Minimal Model Generation. In International Conference on Principles and Practice of Constraint Programming, pages 596-614. Springer, 2017.
17. [Spears and De Jong, 1995] W. M. Spears and K. D. De Jong. On the Virtues of Parameterized Uniform Crossover. Technical report, Naval Research Lab, 1995.
18. [Syswerda, 1989] G. Syswerda. Uniform Crossover in Ge- netic Algorithms. In International Conference on Genetic Algorithms, pages 2-9, 1989.
19. [Terra-Neves et al., 2017] M. Terra-Neves, I. Lynce, and V. Manquinho. Introducing Pareto Minimal Correction Subsets. In International Conference on Theory and Ap- plications of Satisfiability Testing, pages 195-211, 2017.
20. [Terra-Neves et al., 2018] M. Terra-Neves, I. Lynce, and V. Manquinho. Stratification for Constraint-Based Multi- Objective Combinatorial Optimization. In International Joint Conference on Artificial Intelligence, pages 1376- 1382, 2018.
21. [Ulungu and Teghem, 1994] E. L. Ulungu and J. Teghem. Multi-Objective Combinatorial Optimization Problems: A Survey. Journal of Multi-Criteria Decision Analysis, 3(2):83-104, 1994.
22. [Xiang et al., 2018] Y. Xiang, Y. Zhou, Z. Zheng, and M. Li. Configuring Software Product Lines by Combin- ing Many-Objective Optimization and SAT Solvers. ACM Transactions on Software Engineering and Methodology, 26(4):14:1-14:46, 2018.
23. [Zhang and Li, 2007] Q. Zhang and H. Li. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decom- position. IEEE Transactions on Evolutionary Computa- tion, 11(6):712-731, 2007.
24. [Zheng et al., 2016] Q. Zheng, R. Li, X. Li, N. Shah, J. Zhang, F. Tian, K. Chao, and J. Li. Virtual Ma- chine Consolidated Placement Based on Multi-objective Biogeography-based Optimization. Future Generation Computer Systems, 54:95-122, 2016.
25. [Zitzler and Künzli, 2004] E. Zitzler and S. Künzli. Indicator-Based Selection in Multiobjective Search. In International Conference on Parallel Problem Solving from Nature, pages 832-842, 2004.
26. [Zitzler, 1999] E. Zitzler. Evolutionary Algorithms for Mul- tiobjective Optimization: Methods and Applications. PhD thesis, University of Zurich, Zürich, Switzerland, 1999.