# modelling_diversity_of_solutions__5427ba97.pdf

The Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence (AAAI-20)

Modelling Diversity of Solutions

Linnea Ingmar,1 Maria Garcia de la Banda,2 Peter J. Stuckey,2 Guido Tack2

1KTH Royal Institute of Technology, Sweden 2Monash University, Melbourne, Australia lingmar@kth.se, {maria.garciadelabanda, peter.stuckey, guido.tack}@monash.edu

For many combinatorial problems, ﬁnding a single solution is not enough. This is clearly the case for multi-objective optimization problems, as they have no single best solution and, thus, it is useful to ﬁnd a representation of the nondominated solutions (the Pareto frontier). However, it also applies to single objective optimization problems, where one may be interested in ﬁnding several (close to) optimal solutions that illustrate some form of diversity. The same applies to satisfaction problems. This is because models usually idealize the problem in some way, and a diverse pool of solutions may provide a better choice with respect to considerations that are omitted or simpliﬁed in the model. This paper describes a general framework for ﬁnding k diverse solutions to a combinatorial problem (be it satisfaction, single-objective or multi-objective), various approaches to solve problems in the framework, their implementations, and an experimental evaluation of their practicality.

Introduction The vast majority of the literature on optimization focuses on ﬁnding a single optimal solution to a given optimization problem. However, many optimization models only approximate the complex real-word problem they are modelling, and they cannot capture all of the problem details. Hence, the single best solution presented to the problem owner may be far from being the best alternative in practice. The same applies to satisfaction problems, which can be seen as optimization problems with a single, constant optimization function. Ideally, the problem owner would be presented with a set of optimal solutions, to either choose one based on preferences that were not modelled, or to at least get an overview of the range of possible optimal solutions. To overcome this issue one cannot simply provide the problem owner with all optimal solutions to the problem, since that would often be overwhelming and computationally impractical. Similarly, one cannot simply provide a small number of arbitrary optimal solutions, since there is nothing preventing them from being almost identical (e.g., identical except for a single decision that has no impact on

Copyright c 2020, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

the objective value). Instead, one should provide a reasonably small number of diverse solutions that are optimal or close to optimal. This immediately raises the question: what does it mean for solutions to be diverse? A common case for diversity appears in multi-objective optimization problems, where we are presented with several objectives (rather than a single one) to maximize. This naturally gives rise to diversity issues since, while the ideal answer to a multi-objective problem is the entire Pareto frontier or efﬁcient set of solutions, in practice this set is often extremely large. Instead, we aim to ﬁnd k solutions that are diverse with respect to the different objectives. Example 1. Consider the problem of designing the physical layout of a complex chemical plant. The aim is to allocate the position of all equipment and to route the connecting pipes, while ensuring the solutions satisfy different safety and operational constraints, and minimize three cost objectives: footprint, pipes and supports. While the problem relies on uniformly modelling these costs using present values, they are estimations that depend on future unknowns, and might vary independently of each other. If we present a single optimal design to the plant engineers, they are locked into estimations that might be substantially different to what is ﬁnally used. Hence, a better approach is to present them with k diverse designs that are optimal (or near-optimal) in terms of estimated cost, but are substantially different in how those costs are spread among the three objectives. This gives decisions makers the ability to choose a robust solution with respect to their understanding of the relative costs of each component.

While multi-objective problems give rise to a natural notion of diversity, the diversity of solutions may also depend on factors not captured by the objective. Such a notion of diversity is important to all combinatorial problems, including satisfaction and single-objective problems. Example 2. Consider the plant layout problem introduced in Example 1. It is common for plants to have a special piece of equipment (the pipe rack) that traverses the entire plant. The relative position of equipment to this rack is a decision that is often not subject to operational constraints and is thus not captured by any of the objectives. However, some relative positions may be more suitable than others, as they

might affect maintenance access, footprint shape and construction capabilities. Hence, for any given combination of objective values, it makes sense for the plant engineer to explore solutions that differ on the relative position of the equipment. This notion of diversity is not captured by the model s objective function.

The above example shows that measures of diversity are often intimately tied to the model of the problem. Solution diversity in optimization has been studied extensively (see the discussion of related work at the end of this paper). However, current constraint modelling languages do not let modellers directly specify diversity in the model. This paper shows how to extend a solver-independent modelling language to express a very general form of diversity problem. It then deﬁnes a number of approaches to solving this diversity problem, and provides an experimental evaluation of an implementation of the framework that demonstrates the versatility of the diversity problem we deﬁne, and compares the different solving approaches. In particular, the contributions of this paper are:

A generic framework to specify diverse solution problems.

Generic solving approaches to solve the diverse solution problem.

A practical implementation of the diverse solution problem speciﬁcation and their solving approaches in the Mini Zinc (Nethercote et al. 2007) system.

Experimental results showing

The practicality of the framework. The relative strengths and weaknesses of the different solving approaches. Its use on a large real-world optimization problem where diversity has been requested by the industrial clients.

Preliminaries Given a universe of variables V and a set of values D, a valuation θ is a mapping from v V to θ(v) D. Given a set Σ of functions f mapping D D D, we extend θ to map terms over Σ V in the obvious manner θ(f(t1, . . . , tn)) = f(θ(t1), . . . θ(tn)). Similarly, given a set Π of predicates in D D, we extend θ to map atoms of Π over terms in Σ V as θ(p(t1, . . . , tn)) = true iff (θ(t1), . . . , θ(tn)) p. A constraint satisfaction problem (CSP) P = (V, D, C) consists of a set of variables V , an initial (ﬁnite) domain D which maps each variable v V to its set of possible values D(v), and a set of constraints C over variables V . A valuation θ is a solution of P iff θ(v) D(v), v V and θ(c) is true for all c C. A constraint optimization problem (COP) P = (V, D, C, O) consists of a CSP (V, D, C) and an objective function O deﬁned on variables V to be maximized (without loss of generality). An optimal solution of P is a solution θ of (V, D, C) such that for all other solutions θ of (V, D, C), θ(O) θ (O).

A multi-objective constraint optimization problem (MCOP) P = (V, D, C, O) is a COP, where the objective O is replaced by a set of objectives O. Solution θ1 of P dominates solution θ2 if for each O O, θ1(O) θ2(O), and for at least one O O, θ1(O) > θ2(O). A non-dominated solution θ of P is a solution of P that is not dominated by any other solution of P. The Pareto frontier PF(P) of an MCOP P is the set of all non-dominated solutions of P, and provides a picture of the whole space of best solutions. This is useful for problem owners, as it allows them to choose the best tradeoff between the objectives. Since for many MCOPs the Pareto frontier may be too large to compute, we are interested in approximating it by a (small) subset R PF(P). There are different ways to measure how well a Pareto frontier is approximated by subset R. One of the simplest measures is given by the hypervolume of the dominated objective space (Zitzler et al. 2003). Given bounds l O..u O for each objective O O, the hypervolume (HV) measures how many valuations in the hypercube deﬁned over the objectives, are dominated by the solutions in R.

HV = |{(x1, . . . , xn) | xi l Oi..u Oi, θ R : i 1..n : θ(Oi) xi}|

This deﬁnition of HV assumes discrete objectives; a similar deﬁnition using integration exists for continuous domains.

Modelling Diversity This section ﬁrst introduces the various components that make up our diversity framework, and then formally deﬁnes the general diversity problem.

Distance Measures Central to the modelling of solution diversity is a modelspeciﬁc notion of distance between solutions. A distance function δ(θ1, θ2) returns the distance from valuation θ1 to valuation θ2. Note that such a distance function is directional and, thus, may not be symmetric (δ(θ1, θ2) = δ(θ2, θ1)), although symmetry often holds. Example 3. Consider a model M of the plant layout problem introduced in Example 1 expressed in the Mini Zinc modelling language. We can add to M the notion of diversity introduced in Example 2 as follows: enum POS = OVERLAP, NORTH, SOUTH ; array[EQUIPMENT] of var POS: rel_pos_rack; where POS is an enumerated type representing whether equipment overlaps with the rack or is located north or south of it, EQUIPMENT was deﬁned in M as the set of equipment we are trying to position, and rel pos rack is an array of auxiliary decision variables that map every piece of equipment to its relative position with the rack. Note that the above deﬁnitions are added to the model M only to measure solution diversity; they play no role in solving the problem. We can now add to M a distance function (swaps), which given the array of relative positions for two solutions (rpr1 and rpr2), returns the total number (sum) of nonrack equipment (e != rack idx) that swap their relative position from north to south, or from south to north:

var int: swaps(array[int] of var POS: rpr1, array[int] of var POS: rpr2) = sum (e in EQUIPMENT where e != rack_idx) (rpr1[e]!=OVERLAP / rpr2[e]!=OVERLAP / rpr1[e]!=rpr2[e]); Note that this particular distance function is symmetric.

Combining Distances into a Single Diversity Measure There is often more than one single distance function to measure the diversity of solutions. This is common, for example, in multi-objective problems, as each objective provides a diversity measure. Example 4. Consider a radiation scheduling problem with two objectives: minimizing the beamtime of each radiation beam shot, and minimizing the number K of beam shots. These objectives can be expressed in Mini Zinc (using maximization to comply with the framework) as: solve maximize -Beamtime; solve maximize -K; % number of shots The following distance measures can be automatically derived from these objectives: δbeamtime(θ1, θ2) = θ1( Beamtime) θ2( Beamtime) and δshots(θ1, θ2) = θ1( K) θ2( K). Note that these are asymmetrical distance functions: a positive distance δO(θ1, θ2) reﬂects that θ1 is better than θ2 in objective O.

When multiple distance measures Δ = [δ1, . . . , δn] exist, modellers must combine them to create a single diversity measure. Obvious choices for this include using: max: the maximum of the distance measures; : summing up the distance measures; min: the least distance measure, which is useful for ensuring a minimum level of diversity across all measures; lex: a lexicographic order on some ordering of the distance measures, which is useful to make each measure more important than those later in the order. In addition, there might also be problem-speciﬁc ways to combine the measures. In general, given a combinator function C : range(δ1) range(δn) X deﬁned by the modeller to map distances Δ = [δ1, . . . , δn] to some ordered set X, our framework deﬁnes the diversity measure as H(θ1, θ2) = C(δ1(θ1, θ2), . . . , δn(θ1, θ2)). Example 5. For multi-objective problems, a useful way of combining (maximization) distance measures is C = max. This has the property that H(θ1, θ2) > 0 implies there is some distance measure where θ1 is better than θ2 and, hence, θ1 is not dominated by θ2. Similarly, H(θ1, θ2) < 0 implies that θ1 is dominated by θ2.

Intra-diversity Constraints For optimization problems, it is often useful to ﬁnd a diverse set of solutions that are near optimal, since this will eliminate diverse solutions that are not interesting to the problem owner (too far from optimal). The deﬁnition of how near a solution must be to the optimal value to be acceptable is usually problem-speciﬁc and, hence, should be speciﬁed in the

model. Given an optimal or best known solution to a COP with objective value o, our framework requires the deﬁnition in the model of an intra-diversity constraint q(o, O), which constrains the objective O to be near the optimal value o.

Example 6. A common intra-diversity constraint for a COP is to allow solutions within x% of optimal, e.g. q(o, O) = 100O (100 x)o.

A similar intra-diversity constraint q(o, O) can be deﬁned for multi-objective problems, where o contains the optimal value oi for each objective Oi in the multi-objective O.

Example 7. A typical intra-diversity constraint for a multiobjective problem would be to allow solutions within x% of optimal in at least one measure, e.g. q(o, O) = Oi O100Oi (100 x)oi.

Inter-diversity Constraints

When searching for a set of k diverse solutions, there may be a priori restrictions on how different the solutions need to be. Typically, these constraints make use of some distance measure in order to separate the solutions. Hence, the framework includes an inter-diversity constraint p(δ1(θ1, θ2), . . . , δn(θ1, θ2)), which can impose constraints on the various distance measures between solutions.

Example 8. Consider the radiation scheduling problem of Example 4, with the distance measures δbeamtime and δshots. In order to make the solutions noticeably different, modellers may require δbeamtime to be at least 5 minutes, since otherwise the two solutions may not really be different from a patient s perspective. Thus, we deﬁne p(db, ds) as db 300, forcing the beamtimes to differ by at least 300 seconds.

Aggregation of Diversity

In order to select the most diverse k solutions for a problem, our framework uses an aggregator function A to combine the pairwise diversity measures resulting from each pair of solutions, into an overall measure of diversity for the k solutions. Two common deﬁnitions for A are: , summing up the pairwise diversity measures; and min, taking the minimum over all pairs of the diversity measure. For multi-objective problems, the automatically derived aggregator A is min.

The General Diversity Problem

Let us now specify a general framework for deﬁning diversity problems.

Deﬁnition 1 (General Diversity Problem). Given COP P = (V, D, C, O) or MCOP P = (V, D, C, O), a set of pairwise distance functions Δ = {δ1, . . . , δm}, a combinator function C, an aggregator function A, an inter-diversity constraint p and an intra-diversity constraint q, the general diversity problem Q = (P, Δ, C, A, p, q) for non-negative integer k, is to ﬁnd a set Θ such that:

|Θ| = k; θ Θ: θ is a solution to the corresponding CSP (V, D, C);

θ Θ: either q(o, θ(O)) or q(o, θ(O)) holds, where o is the value of the best known solution for COP P, and o contains the values oi of the best known solution for each objective Oi O of MCOP P; θ1, θ2 Θ, θ1 = θ2: p(δ1(θ1, θ2), . . . , δm(θ1, θ2)) holds; and A({C(δ1(θ1, θ2), . . . , δm(θ1, θ2))|θ1, θ2 Θ, θ1 = θ2}) is maximized. Note that not all these features need to be used. For example, if the original problem is a satisfaction problem, then modellers can simply set O = 0 to make it a COP. If they do not want to restrict solutions to be near optimal, they can deﬁne q to be true. Similarly, if they have no a priori distance requirements between solutions, they can deﬁne p to be true.

Solving Diversity Problems This section discusses four approaches to solving the general diversity problem Q = (P, Δ, C, A, p, q) for size k, where P = (V, D, C, O), as per Deﬁnition 1.

Exact Solution Method The most straightforward solving approach is to treat the general diversity problem as a COP and obtain an exact solution. To do this we ﬁrst create k copies of its variables and constraints, k copies of its intra-diversity constraint q, and k(k 1)/2 copies of its inter-diversity constraint p. We then construct the objective function, which is of size |Δ|k(k 1)/2, and solve it using any available constraint optimization solver. The exact solution method, which we denote as EX(k), is the only method we will explore that has the capability of ﬁnding an optimal solution to Q for k. While the problem size of the such COP explodes by at least a factor k, and possibly k2, it can be useful as a component in hybrid and post hoc approaches (see below).

Greedy Solution Method To overcome the size explosion of EX(k), we use a greedy approach that ﬁnds one solution at a time, making use of the components in Q to drive towards diverse solutions. While this greedy method may not ﬁnd optimal solutions to the general diversity problem, it can be much faster in practice, while still producing good diversity. The greedy approximation method GR(k) is shown in Algorithm 1, which iteratively builds a set of solutions Θ as follows. Initially, Θ consists of an arbitrary ﬁrst optimal solution θ1. Then, in each iteration of the loop, a modiﬁed version of the base problem is solved: the set V of variables for the pairwise distances between solutions with their respective domains is joined with V ; the domain D mapping each variable v V is added to D; the set C of constraints on the pairwise distances are added; and the objective is to lexicographically maximize ﬁrst the aggregated distance, and then the original objective O. In other words, in each iteration the most diverse solution is found so that its objective value is at least as good as any other solution with the same diversity. If the original problem P is multi-objective, we create a single objective O =

Oi O wi Oi by weighting

the components with some positive weights wi. In this case, the second component will eliminate dominated solutions.

Algorithm 1 A greedy algorithm for the general diversity problem

1: procedure GR(k) 2: Input General diversity problem Q = ((V, D, C, O), Δ = {δ1, . . . , δm}, A, C, p, q) Non-negative integer k 3: θ1 solution to (V, D, C) that maximizes O 4: o θ1(O) 5: Θ {θ1} 6: while |Θ| k do 7: let θ Θ, δ Δ : dθ δ δ(V, θ(V )) 8: V {dθ δ|θ Θ, δ Δ} 9: C

θ Θ{p(dθ δ1, . . . , dθ δm)} {q(o, O)} 10: θ solution to (V V , D D , C C ) lexicographically maximizing [A({C(dθ δ1, . . . , dθ δm) | θ Θ}, O] 11: Θ Θ {θ} return Θ

The role of the lexicographic optimization is to ensure that the solutions we return are the best of those with the same diversity measure. Consider Example 6, which deﬁnes an intra-diversity constraint requiring solutions to be no more than x% away from the optimal. Without lexicographic optimization, the greedy algorithm could always return solutions that are exactly x% non-optimal, even if optimal solutions with the same measure of diversity exist. Example 9. When solving the radiation scheduling problem of Example 4 using GR(k), the automatically derived aggregated diversity measure in line 10 of Algorithm 1 is: min({max(δbeamtime(V, θ), δshots(V, θ)) | θ Θ}). By maximizing this measure, the algorithm is guaranteed to ﬁnd the worst represented point (Masin and Bukchin 2008) on the Pareto frontier in each iteration.

Hybrid Diversity Solving The GR(k) method is blind to the overall space of solutions. Hence, it can have difﬁculty ﬁnding good solutions. In contrast, the EX(k) method ﬁnds optimal solutions but is inefﬁcient as k grows large (as we will see in the experiments, it is not too bad for a small k). This gives us the impetus to develop a hybrid solving method that combines these two. We can straightforwardly achieve this by deﬁning a HY(l, k), l k method that ﬁrst solves EX(l) to generate the most diverse l solutions, and then uses the greedy method to ﬁnd the next k l solutions, by simply replacing Θ at line 5 of GR(k l) by the result of EX(l).

Post hoc Diversity Solving Previous methods compute exactly k solutions. A different approach to tackling the diversity problem is to compute many more solutions (hopefully, very quickly) and select k diverse solutions from them. More formally, the post

1 % Define a pairwise distance function on x

2 annotation diverse(array[int] of var $T: x,

3 ann: dist_fun);

4 % Define the combinator function

5 annotation div combinator(ann: comb_fun);

6 % Define the aggregator function

7 annotation div aggregator(ann: agg_fun);

8 % Post the intra diversity constraint p

9 annotation intra div constraint(ann: pred);

10 % Post the inter diversity constraint q

11 annotation inter div constraint(ann: pred);

Figure 1: Mini Zinc annotations for diversity.

hoc solving method PH(U, K, k) ﬁrst ﬁnds u > k solutions S, using method U, to CSP (V, D, C {q(o, O)}), and then solves the general diversity problem with the restriction that Θ S, using method K. Note that we can precompute δ(θ1, θ2), δ Δ, θ1, θ2 S, θ1 = θ2 and p(δ1(θ1, θ2), . . . , δm(θ1, θ2)), θ1, θ2 S, θ1 = θ2, where Δ = {δ1, . . . , δm}. Hence, the problem becomes one of selecting k out of u elements of a set, subject to some pairwise constraints and an objective. We can use any approach U to generate the u initial solutions, and any solving method K for selecting k solutions. Obvious choices are random or greedy methods for U, and exact or greedy ones for K.

Implementation in Mini Zinc

Mini Zinc (Nethercote et al. 2007) is a very expressive solver independent modelling language. Therefore, it is not difﬁcult to extend Mini Zinc to deﬁne our general diversity problem. We do so by adding annotations to the model in such a way that, if the annotations are ignored, the model speciﬁes the original COP or MCOP. Figure 1 presents the Mini Zinc annotations added to the Mini Zinc annotation library for modelling the general diversity problem of Deﬁnition 1. Note that we do not need to explicitly model the number of solutions k, as Mini Zinc already supports the setting of a desired number of solutions. Given a model M of a COP or MCOP problem, modellers use Mini Zinc functions (Stuckey and Tack 2013) to deﬁne different distance measures in M. Then, they add to M a diverse annotation (lines 2 3) for each distance measure, where the second argument is the name of the function, and the ﬁrst is the argument to the function (assumed here to be a single array x of variables, all of type T). Modellers also use Mini Zinc functions to deﬁne combinator and aggregator functions in M, and then add div combinator and div aggregator annotations (lines 5 and 7) for these functions. Modellers can then use Mini Zinc predicates to deﬁne the intraand inter-diversity constraints of the problem, and add intra div constraint and inter div constraint annotations (lines 9 and 11) for them. The implementation builds an appropriate Mini Zinc model for the chosen solution approach. For the exact approach it builds one large model. For the greedy and hybrid approaches it builds a new model for each loop iteration.

For the post hoc approach it builds a set selection model, precomputing as much as possible.

Experimental Evaluation Single Distance Measure Consider the Bulk Water Management Problem, which models water reservoirs and bulk transfers over a certain time horizon of multiple years, deployed for a major metropolitan area. Part of the problem is deciding how much water is stored in each reservoir r on each month m: this value is modelled by the two dimensional array of decision variables vol stored. While the total volume stored in all of the reservoirs is close to constant at any given point in time, the stored volume for a given reservoir might vary over time. To model for diversity in volume difference, we introduce an array vol diff of auxiliary decision variables modelling the maximal difference in stored volume for each reservoir:

array[SOURCES] of var 0.0..max_vol: vol_diff = [ max(vol_stored[r,..]) - min(vol_stored[r,..]) | r in SOURCES ]; We use the following diversity annotations:

:: diverse(vol_diff, manhattan); :: div aggregator(min); :: intra div constraint(gap); predicate gap(float: optimal_value) = Obj <= optimal_value + 0.1; where manhattan is a distance function for the Manhattan distance of two arrays of variables, and gap constrains the objective to be equal to the optimal value, using a ﬂoating point precision of 0.1. Table 1 shows runtime and minimum distance between any two solutions of the Bulk Water Management Problem for ﬁve different solving approaches: greedy; exact; hybrid HY(2, k); and two post hoc approaches. Post hoc approach PH(GR, EX, k) (column 4) spends 29 minutes generating a pool Sgreedy of solutions using the greedy approach, and then uses the exact approach to select the k most diverse solutions out of Sgreedy. The post hoc approach PH(RD, GR, k) (column 5) spends 29 minutes generating a set Srandom of random solutions to the problem, and then uses the greedy approach to select k solutions from Srandom. We use the greedy approach in the selection phase, as the exact approach runs out of memory due to the size of Srandom. As the results for the greedy and post hoc approaches depend on the ﬁrst solution, the table shows the mean and standard deviation of diversity over 10 runs using different random start solutions for them. The Bulk Water Management Problem is linear and, thus, it is most efﬁciently solved by a MIP solver; we choose Gurobi. However, for the selection phase of PH(GR, EX, k) we use a CP solver (Gecode), as the selection problem does not linearize well. We produce random solutions in Gurobi by passing a different random seed in each invocation of the solver. Note that while this does not guarantee that solutions are uniformly distributed, it is often the only method of randomisation available in black-box solvers such as Gurobi. As expected, the fastest approach is the greedy one. The exact approach cannot prove optimality within the given

Table 1: Runtime in seconds and solution diversity for the Bulk Water Management Problem using ﬁve solving approaches for ﬁnding k diverse solutions. Symbol indicates the timeout (30 minutes) is reached and the best found diversity before timing out is reported. GR(k) EX(k) HY(2, k) k time div time div time div

2 3.2 202K 3K 106.7 260K 106.0 260K 3 5.0 157K 4K 189K 113.7 140K 4 9.7 122K 2K 156K 118.7 139K 5 12.8 116K 4K 137K 118.3 130K 6 15.6 112K 4K 115K 121.4 116K 7 20.5 102K 3K 93K 132.5 97K 8 27.4 96K 4K 99K 138.5 90K 9 31.9 90K 2K 74K 146.4 90K 10 40.6 84K 2K 60K 155.3 90K 11 45.3 82K 2K 64K 159.2 82K 12 60.4 79K 2K 57K 173.0 80K PH(GR, EX, k) PH(RD, GR, k) k time div time div

2 1740.3 236K 7K 1740.0 86K 5K 3 1740.3 160K 6K 1740.0 60K 6K 4 1740.3 129K 3K 1740.0 55K 5K 5 1740.3 118K 3K 1740.1 43K 3K 6 1740.3 114K 3K 1740.1 40K 3K 7 1740.3 105K 3K 1740.1 37K 2K 8 1740.4 97K 2K 1740.1 35K 2K 9 1740.4 91K 2K 1740.2 34K 2K 10 1740.4 85K 2K 1740.2 31K 3K 11 1740.4 81K 3K 1740.2 30K 3K 12 1740.4 78K 3K 1740.3 27K 2K

timeout for k 2, but ﬁnds the highest solution diversity for k 5 and k = 8. HY(2, k) and PH(GR, EX, k) sometimes ﬁnd solutions of higher diversity than the greedy approach, but have worse runtime. The diversity found by PH(RD, GR, k) is consistently less than half the diversity of the other approaches.

Multiple Distance Measures Consider the Resource-Constrained Project Scheduling Problem with Weighted Earliness/Tardiness objective (RCPSP/WET) (Vanhoucke, Demeulemeester, and Herroelen 2001) as a MCOP problem, where the two objectives are minimizing the earliness and the tardiness of the tasks. The diversity measure is automatically derived (see Example 4) from the two objectives: maximize earliness; and maximize tardiness. Furthermore, the combinator C is min and aggregator A is max (automatically derived). Table 2 shows runtime and hypervolume for the RCPSP/WET problem using three solving approaches for the general diversity problem: the greedy approach and two post hoc approaches. The post hoc approaches use all Pareto optimal solutions S found within 29 minutes by (a) the greedy approach, and (b) random search, and then select the k most diverse solutions from S. The random search

Table 2: Runtime in seconds and hypervolume for the RCPSP/WET problem using four solving approaches for ﬁnding k diverse solutions. Symbol indicates the timeout (30 minutes) is reached and the best found hypervolume before timing out is reported. GR(k) PH(GR, EX, k) k time HV time HV

3 10.6 13.69K 1740.9 13.90K 4 16.9 17.23K 1741.1 17.39K 5 20.5 18.78K 1741.1 19.02K 6 32.2 19.77K 1741.1 19.98K 7 37.2 20.56K 1741.2 20.59K 8 41.6 20.96K 1741.3 21.00K 9 52.2 21.26K 1741.6 21.29K 10 65.9 21.49K 1741.5 21.61K PH(RD, EX, k) Max HV k time HV time HV

3 1740.3 13.90K 273.4 13.94K 4 1740.3 17.40K 17.33K 5 1740.4 19.14K 18.61K 6 1740.4 19.81K 16.61K 7 1740.4 20.58K 13.83K 8 1740.4 21.08K 16.17K 9 1740.4 21.22K 9.15K 10 1740.4 21.71K 0.83K

is done by repeatedly minimizing the weighted sum of the objectives using random positive weights. Note that while the greedy approach guarantees all solutions found so far are Pareto optimal (Masin and Bukchin 2008), the same does not hold for the exact solving approach EX(k). The inter-diversity constraint q would need to be the solution is Pareto optimal , which is not possible to express in a constraint. Therefore, we also compare with a direct approach, named Max HV, which is not part of our framework and ﬁnds k solutions such that the hypervolume measure is maximized. By construction, an optimal solution is guaranteed to consist of a set of Pareto optimal solutions. All approaches are given the two extreme points as start solutions. We use Chuffed as backend solver. Clearly the greedy approach can effectively ﬁnd good representatives of the Pareto frontier quickly. The post hoc approaches ﬁnd in general somewhat better solutions, using more time. The direct approach is competitive with the other approaches in terms of hypervolume for k 5, but does not scale to higher values of k.

Case Study: Process Plant Layout Optimization Consider again the plant layout problem introduced in Example 1, modelled using (a) the state-of-the-art model of the problem deﬁned by Belov et al. (2018), and (b) the deﬁnition of diversity based on the relative positions of the rack as discussed in Example 3. The diversity annotations are:

:: diverse(rel_pos_rack, swaps); :: div aggregator(min); :: intra div constraint(within_five_percent);

Figure 2: Three diverse solutions to the process plant layout problem.

where within five percent constrains the objective to be within ﬁve percent of the optimal value. For demonstration purposes, we use a subset of a real world instance with 20 (out of more than 200 in total) pieces of equipment. While the full instance cannot be solved to optimality even within 2 weeks, our small instance takes less than one minute to solve to optimality using Gurobi on 4 threads. Figure 2 shows a top-down view of three plant designs, where the large dark grey area in each solution is the pipe rack, and the smaller rectangles are other pieces of equipment. All solutions are generated with the greedy approach, using the above diversity annotations. Clearly, the user is presented with three very different designs.

Related Work and Conclusion

The diversity of solutions has been studied in the context of constraint programming (CP) (Hebrard et al. 2005; Hebrard, O Sullivan, and Walsh 2007; Petit and Trapp 2015), mixed integer programming (MIP) (Glover, Løkketangen, and Woodruff 2000), Boolean satisﬁability (SAT) (Nadel 2011) and answer set programming (ASP) (Eiter et al. 2009), among others. The key design principle of our work is to separate modelling of diversity problems from how they are solved, while in most previous work modelling and solving are conﬂated. An exception is work by Hebrard et al. (2005), which introduces several classes of diversity (and similarity) problems for constraint satisfaction, as well as two generic ways of solving such problems. Perhaps their most important problem class is MAXDIVERSEk SET, which aims to ﬁnd k solutions, such that the minimum distance between any two solutions is maximized, for a given distance measure. The general diversity problem from Deﬁnition 1 is a generalization of MAXDIVERSEk SET, as we consider (multi-objective) optimization problems, support the deﬁnition and combination of different distance measures, and of constraint solutions with user-deﬁned intraand interdiversity constrains. Similarly, the two solving algorithms proposed by Hebrard et al. (2005) are special cases of the greedy and exact approaches discussed in this paper. The work by Petit and Trapp (2015) generalizes Hebrard et al. s greedy algorithm to single objective problems. To ﬁnd solutions that are diverse as well as near optimal, the ratio of diversity and loss in optimality is maximized in each iter-

ation. Their algorithm allows threshold values on optimality and diversity to be speciﬁed, which is similar in idea to our intraand inter-diversity constraints. Their algorithm is, however, implemented directly into a solver without a clear separation between modelling and solving. Our work clearly distinguishes itself from this work, and all the other ones we are aware of, by providing an easy-to-use modelling framework where various diversity components can be deﬁned in an expressive modelling language directly in the model, independently of how the problem is solved. Work has been done for ﬁnding diverse solutions in speciﬁc solving technologies. This includes, for example, papers by Hebrard et al. (2005) and Hebrard, O Sullivan, and Walsh (2007), which introduce global constraints and propagation algorithms for CP, and work by Glover, Løkketangen, and Woodruff (2000), which is speciﬁc for MIP. Although the aim of our work is to be solver-independent, future work should include how these methods can be utilized by our framework when using a certain solving technology. In population based methods, such as evolutionary algorithms, maintaining diversity in the population pool is needed to prevent premature convergence to a sub-optimal solution, and can be achieved by so called niching methods (Li et al. 2017). Niching can also be used for ﬁnding several diverse solutions (see e.g. Kruisselbrink et al. 2009). Whether ideas from niching methods can be reused in our framework, is an interesting research direction. To the best of our knowledge, there is no previous work that combines Pareto optimality with solution diversity. However, there are many algorithms in the literature for solving MCOPs in general. Many such algorithms are designed for enumerating the complete Pareto frontier, such as the widely studied ϵ-constraint method (Y. Haimes, Lasdon, and A. Wismer 1971) and a recently proposed decision diagram method (Bergman and Cir e 2016). More related to our focus on diversity is previous work on ﬁnding representative subsets of the Pareto frontier. An overview of such algorithms for continuous optimization problems was recently done (Burachik, Kaya, and Rizvi 2019), and whether any of them can be used in our framework should be investigated in future work. Two studies that focus on discrete problems are by Schwind et al. (2016) and by Masin and Bukchin (2008). The former considers the problem of ﬁnding a subset of a given size k of the Pareto frontier, such that a measure of representativity is maximized, and prove the decision version of the problem to be ΣP 2-complete. The latter ﬁnds a representative set by iteratively adding the worst represented point on the Pareto frontier. Notably, their algorithm is a special case of Algorithm 1.

Conclusion We deﬁne a modelling framework for solving diversity problems and a number of solving methods to tackle these problems. This allows a modeller to add measures of diversity to their model in a straightforward way, and to collect a diverse set of solutions. Experiments show the approach is applicable to large real world problems. It is the ﬁrst modelling framework we are aware of to allow diversity to be directly speciﬁed as part of the model.

Acknowledgements This work was partly sponsored by the Australian Research Council grant DP180100151. The authors would like to thank the anonymous reviewers for their helpful comments, and Ilankaikone Senthooran for providing instances for the case study in the experimental evaluation of this work.

Belov, G.; Czauderna, T.; de la Banda, M. G.; Klapperst uck, M.; Senthooran, I.; Smith, M.; Wybrow, M.; and Wallace, M. 2018. Process plant layout optimization: Equipment allocation. In Hooker, J. N., ed., Proceedings of the Twenty Fourth International Conference on Principles and Practice of Constraint Programming, CP 2018, volume 11008 of Lecture Notes in Computer Science, 473 489. Springer. Bergman, D., and Cir e, A. A. 2016. Multiobjective optimization by decision diagrams. In Rueher, M., ed., Proceedings of the Twenty-second International Conference on Principles and Practice of Constraint Programming, CP 2016, volume 9892 of Lecture Notes in Computer Science, 86 95. Springer. Burachik, R.; Kaya, C.; and Rizvi, M. 2019. Algorithms for generating pareto fronts of multi-objective integer and mixed-integer programming problems. Preprint, http://arxiv. org/abs/1903.07041. Eiter, T.; Erdem, E.; Erdo gan, H.; and Fink, M. 2009. Finding similar or diverse solutions in answer set programming. In Hill, P. M., and Warren, D. S., eds., Proceedings of the Twentyﬁfth International Conference in Logic Programming, ICLP 2009, volume 5649 of Lecture Notes in Computer Science, 342 356. Springer. Glover, F.; Løkketangen, A.; and Woodruff, D. L. 2000. Scatter search to generate diverse MIP solutions. In Laguna, M., and Velarde, J. L. G., eds., Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, volume 12, 299 317. Springer. Hebrard, E.; Hnich, B.; O Sullivan, B.; and Walsh, T. 2005. Finding diverse and similar solutions in constraint programming. In Veloso, M. M., and Kambhampati, S., eds., Proceedings of the Twentieth AAAI Conference on Artiﬁcial Intelligence, 372 377. AAAI Press / The MIT Press. Hebrard, E.; O Sullivan, B.; and Walsh, T. 2007. Distance constraints in constraint satisfaction. In Veloso, M. M., ed., Proceedings of the Twentieth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2007, 106 111. Kruisselbrink, J. W.; Aleman, A.; Emmerich, M. T. M.; IJzerman, A. P.; Bender, A.; B ack, T.; and van der Horst, E. 2009. Enhancing search space diversity in multi-objective evolutionary drug molecule design using niching. In Rothlauf, F., ed., Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2009, 217 224. ACM. Li, X.; Epitropakis, M. G.; Deb, K.; and Engelbrecht, A. P. 2017. Seeking multiple solutions: An updated survey on niching methods and their applications. IEEE Trans. Evolutionary Computation 21(4):518 538.

Masin, M., and Bukchin, Y. 2008. Diversity maximization approach for multiobjective optimization. Operations Research 56(2):411 424. Nadel, A. 2011. Generating diverse solutions in SAT. In Sakallah, K. A., and Simon, L., eds., Proceedings of the Fourteenth International Conference on Theory and Applications of Satisﬁability Testing, SAT 2011, volume 6695 of Lecture Notes in Computer Science, 287 301. Springer. Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; and Tack, G. 2007. Mini Zinc: Towards a standard CP modelling language. In Bessiere, C., ed., Proceedings of the Thirteenth International Conference on Principles and Practice of Constraint Programming, CP 2007, volume 4741 of Lecture Notes in Computer Science, 529 543. Springer. Petit, T., and Trapp, A. C. 2015. Finding diverse solutions of high quality to constraint optimization problems. In Yang, Q., and Wooldridge, M. J., eds., Proceedings of the Twenty Fourth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2015, 260 267. AAAI Press. Schwind, N.; Okimoto, T.; Clement, M.; and Inoue, K. 2016. Representative solutions for multi-objective constraint optimization problems. In Baral, C.; Delgrande, J. P.; and Wolter, F., eds., Proceedings of the Fifteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2016, 601 604. AAAI Press. Stuckey, P. J., and Tack, G. 2013. Mini Zinc with functions. In Gomes, C. P., and Sellmann, M., eds., Proceedings of the Tenth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2013, volume 7874 of Lecture Notes in Computer Science, 268 283. Springer. Vanhoucke, M.; Demeulemeester, E.; and Herroelen, W. 2001. An exact procedure for the resource-constrained weighted earliness-tardiness project scheduling problem. Annals OR 102(1-4):179 196. Y. Haimes, Y.; Lasdon, L.; and A. Wismer, D. 1971. On a bicriterion formulation of the problems of integrated system identiﬁcation and system optimization. IEEE Transactions on Systems, Man, and Cybernetics SMC-1:296 297. Zitzler, E.; Thiele, L.; Laumanns, M.; Fonseca, C. M.; and da Fonseca, V. G. 2003. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evolutionary Computation 7(2):117 132.