Finding Diverse Solutions of High Quality to Constraint Optimization Problems

1 Introduction

Most existing techniques for solving optimization problems in Artificial Intelligence naturally give the priority to the value of an objective function. While this is essential from the optimality point of view, there are scenarios where it may be advantageous to consider multiple solutions. In Constraint Programming (CP), a number of effective methods can be used to generate multiple solutions that are significantly diverse, e.g., [Hebrard et al., 2005; 2007]. However, these techniques deal with satisfaction problems and are not concerned by solution quality, i.e., the value of the objective function of each diverse solution. On the other hand, constraint solvers routinely generate a single solution to optimization problems, ideally optimal. In this paper, we suggest a generic constraintbased paradigm for assessing both solution diversity and solution quality, which can take as argument any constraint optimization problem. Motivated by practical applications, we propose to consider several diversity norms and to use them in conjunction with a quality constraint. In this way, we provide a set of solutions that optimize a compromise between solution diversity and quality. Such a tradeoff is especially useful, for instance, in personnel scheduling (when not all user preferences are known in advance), for routing problems (alternative paths are useful in case of unexpected events), and in configuration (a good quality product can be made using diverse sets of components). As there is no requirement for the initial solution to be optimal, there is therefore no theoretical restriction on solving large problems, using for instance

Andrew C. Trapp

Foisie School of Business, Worcester Polytechnic Institute, USA atrapp@wpi.edu

Large Neighborhood Search. Our approach can easily be implemented in most existing solvers. Moreover, our paradigm can be specialized to produce diverse solutions of high quality in the context of over-constrained problems. A second contribution of our paper is to consider diversity from a different point of view, based on global constraints. The intuitive idea is to propose to the end-user solutions that correspond to some generic concepts, such as concentration or fair distribution of high values, deviation, etc. We show that our paradigm is naturally well-suited to use these new notions, extending the state-of-the art in CP also for satisfaction problems.

2 Background

Constraint Programming. A constraint network N consists of a sequence of problem variables X = (x1, . . . , xn), a sequence of domains D = {D(x1),D(x2), . . . ,D(xn)}, where the domain D(xi) is the finite set of at most d values that variable xi can take (we also use the notation Di), and a set C of constraints that specify the allowed combinations of values for given subsets of variables. A relation R of arity k is any set of tuples 〈a1, a2, . . . , ak〉 where all aj's

are values from the given universe U. A constraint of arity k is a pair C = (X,R), where X is a sequence of k variables and R is a relation of arity k. An assignment t is a function fromX to the universe of values U. t[x] is the value of x in t. An assignment t to a sequence X = (x1, . . . , xk) of variables, or to a superset of X, satisfies C = (X,R) iff 〈t[x1], . . . , t[xk]〉 ∈ R. Otherwise, t violates C. A solution of N = (X,D, C) is an assignment t to X such that t[xi] ∈ Di for all xi ∈ X, and t satisfies all the constraints in C. In a Constraint Optimization Problem (COP), a variable obj ∈ X represents the objective value. Without loss of generality, consider the minimization COP. An optimal solution is then a solution t∗ of the constraint network such that no other solution t exists with t[obj ] < t∗ [obj ]. An alternative way to represent optimization problems is to extend CP, using Semi-ring CSPs/Cost Functional Networks [Bistarelli et al., 1999]. In such frameworks, conversely to classical COP, costs involved in the objective function are not encoded by problem variables. The two alternatives were successfully used for solving real-world problems (see for example [Zampelli et al., 2013; Allouche et al., 2014]). As our contributions in sections 5 and 6 require to set hard constraints on cost variables, in this paper we deal with classical COP.

Solution Quality. Solution quality [Trapp and Konrad, 2015], also called performance [Billaut et al., 2010], aims to measure the distance between the value t[obj] in a given solution t of a COP and the objective value t∗ [obj] of a "good" solution t∗ , ideally an optimal solution. Given the objective variable obj , the relative deterioration of quality of solution t can be quantified using the following function: Q(X , t, t∗ ) = max(0, t[obj ] - t∗ [obj ]).

Solution Diversity. Although in CP solution diversity received less exposure than solution quality, some significant contributions have been made in the last decade. Hebrard et al. [Hebrard et al., 2005] distinguish offline diversity, computed given the whole set of solutions, from online diversity where solutions are computed incrementally. In this paper we will consider online diversity, which is intuitive for COP.

1) Hamming distance. The most usual diversity measure is the sum of Hamming distances [Hamming, 1950].

Definition 1 (Hamming Distance δH) Given two assignments ti and tj of n variables X and xl ∈ X,

• δH(ti[xl], tj[xl]) = 0 iff ti[xl] = tj[xl], 1 otherwise.
• δH(X, ti, tj) = ∑nl=1 δH(ti[xl], tj[xl]).

The MAXDIVERSEkSet problem [Hebrard et al., 2005] consists of finding a set of solutions {t1, t2, . . . , tk} maximizing ∑1≤i<j≤k δH(X, ti, tj). Heuristic approaches [Hebrard et al., 2005; Hentenryck et al., 2009] and knowledge compilation techniques [Hadzic et al., 2009] have been used to solve this problem.

2) Alternative Distance Functions. Depending on the problem and the solving technique, Hamming distances may not be appropriate. For instance, consider a scheduling problem with a horizon of one day and a time unit of one minute. Given a solution, delaying all activities by one minute leads to a diverse solution according to Hamming distances, yet in practice the two solutions are quite similar. Conversely, if we swap the k first and k last activities, even with small values of k the end-user may consider that the new solution significantly differs from the initial one. Following the work of Hebard et al., this observation was made in the context of knowledge compilation [Hadzic et al., 2009] and Answer-set programming [Eiter et al., 2013]. To address this issue in CP, we consider measures based on the L1 and L2 norms.

Definition 2 (Manhattan (δL1 ), Euclidian (δL2 ) distances) Given two assignments ti and tj of n variables X and xl ∈ X,

• δL1 (ti[xl], tj[xl]) = |ti[xl] - tj[xl]|. δL1 (X , ti, tj ) = ∑nl=1 δL1 (ti[xl], tj [xl]).
• δL2 (ti[xl], tj[xl]) = (ti[xl] - tj[xl])2 . δL2 (X , ti, tj ) = √∑nl=1 δL2 (ti[xl], tj [xl]).

3 Assessing Both Diversity and Quality

Simultaneously addressing both diversity and quality requires two objective functions, Q and δ, δ ∈ {δH, δL1 , δL2 }. As the MAXDIVERSEkSet problem is F NP[log(n)] -complete [Hebrard et al., 2005] without regard to quality, we introduce a pragmatic technique for dealing with the two notions at the same time. Just as importantly, we propose a framework that can be easily implemented using reference constraint programming solvers. Following a principle recently suggested for MIP [Trapp and Konrad, 2015], a ratio can be defined to balance between solution quality and diversity. Starting from a "good" solution t∗ , i.e., with an objective value that satisfies the end-user, we consider the following ratio.

We assume in this section that the problem has at least one feasible solution, and subsequently investigate the specific case of over-constrained problems. The goal is to find the set of optimal, or at least high-quality, solutions of a new problem derived from the original one. The new problem maximizes the ratio starting from a solution t∗ . Unlike the MIP paradigm proposed by Trapp and Konrad, however, the solution t∗ may be suboptimal. The first step is to express the relative solution diversity and relative loss of quality according to solution t∗ within the CP framework, in order to obtain a second (diverse) solution t2. Then, iteratively, we will compute the next solution according to the solution set S = {t1 = t∗ , t2} to obtain a third solution t3, and so on.

Relative Solution Diversity. This part of our methodology does not fundamentally differ from the constraint satisfaction case. We use a new problem variable xδ for storing the minimum allowed diversity threshold. In the case of Hamming Distances, we use the DIVERSESUMH constraint [Hebrard et al., 2005]. This constraint takes as argument a set of problem variables, a set of previously computed solutions and the variable xδ. In its initial formulation [Hebrard et al., 2005], xδ is an integer, but we aim to be as generic as possible in the modeling description.

Definition 3 DIVERSESUMH(X , S, xδ) ⇔

We now define similar constraints for L1 and L2 norms.

Some alternative definitions of distance constraints exist for Hamming distances and metrics that are component-wise decomposable like Hamming distances [Hebrard et al., 2005; 2007; 2011]. These feature idempotent operators (minimum, maximum) instead of a sum, or are dedicated to finding sets of similar solutions to satisfaction problems rather than diverse solutions.

Relative Loss of Quality. The relative deterioration in objective function quality can be expressed using a constraint QUALITYSUM(obj , t∗ , xQ), where variable xQ expresses the loss of quality with respect to the first solution t∗ .

ANewMaximization Problem. We introduce a newmaximization problem for simultaneously assessing both diversity and quality. We aim to maximize the ratio xδ xQ+1 in each new produced solution. Our paradigm is based on an iterative scheme, summarized by Algorithm 1. Given a variable x, we use the notation x (respectively x) for the minimum value (respectively the maximum value) in its domain.

Algorithm 1 takes as argument a COP encoded with the constraint network N and an integer k, as well as the two variables xδ and xQ for defining the allowed range of values for the ratio numerator and denominator. The algorithm returns a solution set S of size at most k, maximizing the balance between relative diversity and quality with respect to solutions in S. The initial values xδ and xQ provide the user preferences in terms of minimum acceptable diversity value between two solutions and maximum loss of quality between two solutions. The initial maximum diversity xδ can be easily estimated for each metric, e.g., for the L1 norm an upperbound is the sum of domain sizes, which is convenient in our context. As several optimal solutions may exist, we initially set xQ = 0.

There are several ways to implement the objective constraint in the solving scheme described by Algorithm 1. Therefore, we do not directly express the ratio as stated. We use an objective constraint OPTRATIO(xδ, xQ, robj . . .), where robj is the integer objective variable explicitly maximized. The dots in the signature mean that, depending on the selected implementation, OPTRATIO may require some additional parameters. We will detail this constraint later.

The original objective constraint used to obtain a value for variable obj is never removed from the model. However, except for the first solution, we maximize robj instead of minimizing obj . After having solved the initial problem and identified a solution, the constraints DIVERSESUM and QUALITYSUM control diversity and quality of subsequent solutions through the two variables xδ and xQ.

While a variety of metrics could be used in Algorithm 1, we consider the L1 norm in our pseudo-code. The domain of the diversity variable xδ must be updated each time a new solution is added to the set S, so as to maintain the same global diversity criterion. To illustrate this need, consider a simple example. Assume after the first run producing a solution t1 to

1 t1 := Solution to N minimizing obj ; 2 S := {t1}; 3 j := 1; lbδ := xδ; ubδ := xδ; 4 C := C∪ DIVERSESUML1 (X, S, xδ); 5 C := C∪ QUALITYSUM(obj , t1, xQ); 6 C := C∪ OPTRATIO(xδ, xQ, robj . . .); 7 repeat 8 j := j +1; 9 tj := Solution to N maximizing robj ; 10 xδ := tj[xδ] + j × lbδ; xδ := tj[xδ] + j ×ubδ; 11 S := S ∪ {tj}; 12 until Fail exception ∨ |S| ≥ k; 13 return S;

the initial problem we start searching for a second solution t2 with xδ = 4. Assume t2[xδ] = 5. Then for the third solution t3 we have to consider three of pairs of solutions instead of one (t1 vs t2, t2 vs t3 and t1 vs t3), thus we add 2 ∗ 4 = 8 to the previously counted distance t2[xδ] = 5, which leads to xδ = 13. At the next step, we have six pairs of solutions instead of three, we add 3 ∗ 4 = 12 to t3[xδ], and so on.

Performing a similar update of xQ variable is not necessary, as the quality constraint QUALITYSUM does not deal with the entire solution set S, but rather with the initial objective variable of the problem and the first solution t1.

Concerning time complexity, we define a new but classical COP. The generic framework takes as an argument any COP. The distance measures should be computable in polynomial time for any fixed assignment (this is the case for Hamming, L1 and L2). As the new objective function is linked to the initial objective variable by the quality constraint and no constraints are removed, starting from a NP-Hard COP the resulting problem will generally remain in the same complexity class. However, the domain size of the new objective variable may differ from the size of the original one.

4 Filtering Algorithms

Filtering Diversity Constraints To obtain a satisfactory solving process we need to propagate all the constraints involved in Algorithm 1. We first focus on diversity.

1) Hamming distance. A filtering algorithm for DIVERSESUMH(X , S, xδ) has already been introduced [Hebrard et al., 2005]. This algorithm maintains Generalized Arc Consistency (GAC, see [Bessi`ere, 2006]) in the case where xδ is an integer, in O(n(d + k)) time, with n = |X|, k = |S| and d is the maximum domain size. In our context, the most useful filtering of the constraint is performed according to the minimum current value xδ for variable xδ, thus the algorithm of Hebrard et al. can be adapted in straightforward manner, even handling xδ, and so we omit it for the sake of brevity.

2) L1 norm. We propose an algorithm for the L1 norm that runs in O(k·∑i Di) time, where ∑i Di is the sum of domain sizes of variables in X . We have ∑i Di ≤ n·d but depending on the current domains n · d may be a gross over-estimation. Algorithm 2 takes as arguments the variables, the set S of previous solutions, as well as the value of xδ in the last previous solution, prevxδ . The principle is to remove values that are not consistent with the current bounds of D(xδ) using a regret mechanism, according to the minimum and maximum possible distances. The algorithm eliminates all the values that are not consistent, enforcing GAC.

3) L2 norm. This case is more complex as the distance between two solutions is not computed with a simple sum.

However, we sill can design a propagator (Algorithm 3) in O(k · ∑i Di) time. The principle is first to fill a three dimensional matrix with all squares and then to compute maximum L2 norms between X and each t ∈ S. With such data we can again use a regret mechanism to remove all the values that are not consistent with xδ and xδ , as Algorithm 2 does for L1 norm.

1 foreach i ∈ {1, 2, . . . , n} do 2 foreach vj ∈ D(xi) do 3 dist[i][j] := ∑|S| k=1 |vj - tk[xi]|; 4 maxSum := ∑|X| i=1 max(dist [i]) + prevxδ ; 5 minSum := ∑|X| i=1 min(dist [i]) + prevxδ ; 6 xδ :=min(maxSum, xδ); xδ :=max(minSum, xδ); 7 foreach i ∈ {1, 2, . . . , |X|} do 8 foreach vj ∈ D(xi) do 9 if maxSum - max(dist [i]) + dist [i][j] < xδ then 10 D(xi) := D(xi) \ {vj} ; 11 if minSum - min(dist [i]) + dist [i][j] > xδ then 12 D(xi) := D(xi) \ {vj} ;

1 // Fill a three dimensional matrix with all squares 2 foreach i ∈ {1, 2, . . . , |X|} do 3 foreach k ∈ {1, 2, . . . , |S|} do 4 foreach vj ∈ D(xi) do 5 dist[i][k][j] := (vj - tk[xi])2 ; 6 maxd[i][k] :=maxj(dist[i][k]); 7 mind[i][k] :=minj(dist[i][k]); 8 // Min. and max. L2 norms between X and each t ∈ S 9 maxSum := 0; 10 foreach k ∈ {1, 2, . . . , |S|} do 11 maxSum[k] := 0; 12 foreach i ∈ {1, 2, . . . , |X |} do 13 maxSum[k] :=maxSum[k] +maxd[i][k]; 14 maxSum =maxSum + √maxSum[k]; 15 minSum := 0; . . . Symmetric to maxSum 16 // Filtering 17 maxSum :=maxSum +prevxδ ; 18 minSum :=minSum +prevxδ ; 19 xδ := ⌈min(maxSum, xδ)⌉; xδ := ⌊max(minSum, xδ)⌋; 20 foreach i ∈ {1, 2, . . . , |X|} do 21 foreach vj ∈ D(xi) do 22 nsummax := 0; 23 foreach k ∈ {1, 2, . . . , |S|} do 24 nsummax[k] := maxSum[k] - maxd [i][k] + dist [i][k][j]; 25 nsummax := nsummax + √nsummax[k]; 26 nsummin := 0; . . . Symmetric to maxSum 27 if ⌈nsummax⌉ < xδ then D(xi) := D(xi) \ {vj} ; 28 ; 29 if ⌊nsummin⌋ > xδ then D(xi) := D(xi) \ {vj} ; 30 ;

Filtering the Quality Constraint. Bounds can be sharply adjusted in constant time complexity. As this filtering procedure is obvious and standard in CP, for sake of space we do not present it in this paper. The lower bound of obj is not affected by this constraint.

Propagating the NewObjective. This section investigates the filtering algorithm of OPTRATIO(xδ, xQ, robj . . .), the constraint used to balance between diversity and quality. We suggest two ways for expressing this constraint: Directly defining a ratio, or using a weighted sum.

1) Using a Ratio. We can directly define OPTRATIO(xδ, xQ, robj ) as xδ xQ+1 . However, diversity expressed by variable xδ and quality expressed by xQ variable may be of widely varying scale. Fortunately, we designed our paradigm so that the domain size of xδ does not change. Its lower bound increases after each new solution proportionally to its upper bound. This observation enables straightforward normalization of the computation.

Let |xδ| be the size of D(xδ). Before starting the search of a new solution, we define at each new step j in the loop, that is, after line 8 of Algorithm 1, the two following rounded integer quantities:

Then, we add two variables x′δ and x′Q such that

We add constraints to the model stating that x′δ = f ×xδ and x′Q = g × xQ and we use x′δ and x′Q instead of xδ and xQ in the ratio to obtain a normalized result.

2) Using a Weighted Sum. We define the constraint as follows. Given two positive integers α and β, an assignment of values to variables {xδ, xQ, robj } to constraint OPTRATIO(xδ, xQ, robj , α, β) is satisfied iff: robj = α × xδ - β × xQ. This constraint can be filtered using standard features available in most solvers. To ensure a proper balance between the two factors of the sum, a straightforward adjustment of α or β is all that is required, somewhat simpler than the normalization of a ratio; we just need to augment either α or β. Typically, the diversity values should grow quickly, proportional to the number of solutions in S, notably when we initially have set α = β = 1. Given the last previous solution tj, we suggest in this case to normalize the sum by updating β so as β =max(β, tj[xδ] xQ ). At last, one may consider multiobjective optimization instead of a weighted sum. There are no theoretical issues specific to our approach concerning this alternative methodology.

5 Application to Over-Constrained Problems

A problem is over-constrained when no assignment of values to variables satisfies all constraints. In this situation, constraint violations are allowed in solutions, providing that such solutions retain practical interest. Diversity in this problem class is important, as it is not clear which combinations of violations are acceptable, thus making the anticipation of such rules challenging. Typically, we would like to propose a solution set where the violated constraints are not the same from one solution to another. On the other hand, in these problem violations should still be minimized. The quantity of violations that can be expressed in different ways (number of violations, weights, etc.), measures the quality of solutions.

Petit et al. [Petit et al., 2000] suggested to express an overconstrained problem as a classical optimization problem, using new variables to express violations. These variables can have integer domains if a distance to satisfaction is measured or boolean domains if we solve the Max-CSP, where the objective is to minimize the number of constraint violations. For the sake of simplicity, and without loss of generality, we consider Max-CSP. Let Xv = {xv1, xv2, . . . xv|C|} be the set of boolean violation variables, given the constraint set C. The objective constraint of Max-CSP is obj = ∑|C| i=1 xvi.

Using such a formulation, applying Algorithm 1 with Hamming distances restricted to the set Xv (instead of considering all variables) generates solutions maximizing the balance between the number of constraint violations and the diversity of these violations. The diversity occurs when different constraints are violated in pairs of solutions. No new implementation issues are introduced. We are considering a subset of variables instead of all problem variables X. In this way, our framework adapts to over-constrained problems.

6 An Alternative View of Solution Diversity

Semantics-Based Distance Definitions. Quite often, realworld optimization problems contain constraints that involve the objective function, or at least portions of it. Such constraints express some generic concepts which distinguish useful solutions from solutions that may be optimal with respect to the objective function, but not applicable in practice. In CP, this need was introduced, for instance, in the context of over-constrained problems [Petit et al., 2000] and subsequently by the introduction of several new global constraints, e.g., [Pesant and R´egin, 2005; Schaus et al., 2007; Petit, 2012; Narodytska et al., 2013]. However, end-users are not always able to formulate their respective preferences, even less using global constraints. In this context, we would like a system that is able to propose different classes of solutions, each one corresponding to one particular concept. Following this idea, we propose a new approach for defining diversity. Consider the following example.

Example 1 Let X = 〈x1, x2, . . . , xn=10〉 be a sequence of variables ordered by their indexes, all involved in an objective function ∑ni=1 xi ≤ s to minimize. Consider two solutions of equal quality t1 = 〈1, 0, 0, 1, 0, 0, 1, 0, 0, 1〉 and t2 = 〈0, 0, 0, 1, 1, 1, 1, 0, 0, 0〉. δH(X, t1, t2) = δL1 (X, t1, t2) = 4 and δL2 (X , t1, t2) = 2.

In this example, the two solutions have equivalent quality and they are quite similar, as 60% of variables share the same value. Nevertheless, one may observe that in t1 zero costs are homogeneously distributed in the sequence, whereas in t2 costs equal to 1 are concentrated in a unique area. From the point of view of the end-user, this characteristic may make the two solutions appear very distinct. In CP, the generic concept of concentrating costs is a sequence is captured by FOCUS [Petit, 2012], a counting constraint. By counting, we mean that a particular variable is used to measure a given property, which is here the concentration of high values.

Definition 7 Let si,j be any sequence of indices of consecutive variables in X, such that si,j = [i, i + 1, . . . , j],

1 ≤ i ≤ j ≤ n.

Let yc be a variable. Let k and len be two integers, 1 ≤ len ≤ n. An instantiation of X ∪{yc} satisfies FOCUS(X , yc , len, k ) iff there exists a set SX of disjoint sequences of indices si,j such that three conditions are all satisfied: (1) |SX | ≤ yc. (2) ∀xl ∈ X, xl > k ⇔ ∃si,j ∈ SX such that l ∈ si,j. (3) ∀si,j ∈ SX , j - i + 1 ≤ len.

Assume we do not constrain sequence length (len = n) and k (highest "non costly" value) is equal to 0. Regarding Example 1, the minimum value for yc in t1 is 4, while the minimum value for yc in t2 is 1. This means that solution t2 is more concentrated than solution t1, and we can use this result as a metric for estimating solution diversity. While Example 1 is restricted to constraint networks where the ordering (or more generally the topology) of variables is important, many other concepts are expressed by counting constraints, such as the CHANGE constraint for timetabling [Cosytec, 1997], DEVIATION [Schaus et al., 2007], AMONG [Bessi`ere et al., 2005], BALANCE [Bessi`ere et al., 2014].

Integration in our Framework The simplest way to incorporate this new approach would be to replace the diversity constraint by a given counting constraint. However, it is likely more appropriate and desirable to prioritize classical diverse solutions, e.g., obtained using Hamming-based, L1 or L2 norms, which additionally vary according to the concept captured by a given counting constraint. As generic concepts may be of heterogeneous nature, we may provide a diverse set of solutions for each concept class. Therefore, we suggest to integrate the counting variable yc in the quality constraint QUALITYSUM instead of modifying the diversity approach. This is possible because quality is taken into account in the objective of the new maximization problem. We replace the quality variable xQ in Algorithm 1 by a new variable x′Q, such that x′Q = γxQ + θyc, where γ and θ are positive integers. In the case of satisfaction problems, we may consider only x′Q = yc . Our framework can thus be considered as an extension of previous CP approaches, able to tackle new definitions of diversity for satisfaction and optimization problems.

7 Experiments

We used an IntelXeon 2.27GHz machine and the Choco 3.2.1 solver. 1 We exclusively provided a constraint network as argument without any specific tuning to the problem. We systematically re-use the search strategy of the original model (e.g., DOM/WDEG [Boussemart et al., 2004]), and then assign the new variables in static order. We present the results using the L1 norm for diversity. Other cases are similar.

1) Sorting chords. We implemented the chords musical benchmark [Truchet and Codognet, 2004; Petit, 2012]. Chords have to be sorted in order to minimize a sum of costs. All the chords should be different. Each cost corresponds to two consecutive chords and is equal to the number of notes changing from one chord to the next one less one, plus additional penalties in some cases. A pair of consecutive chords with a non zero cost is a violation.

1 http://www.emn.fr/z-info/choco-solver/

An instance with optimal sum value that is strictly positive is over-constrained. We generated a random cost value for each possible pair of chords. In a first experiment, we compare methods for computing the new objective variable robj , namely a ratio (R), a normalized ratio (NR), a sum with α = β = 1 (S) and a normalized sum (NS). Let nc be the number of chord variables and maxc be the maximum possible value of a cost. For each instance, we give average results obtained with 20 randomly generated cost matrices, and we generate 20 solutions per matrix and ratio, with a time-limit of 15 seconds for each new solution. Moreover, after having generated the first solution t∗ = t1 with objective value t1[obj] and prior to searching for additional solutions, we run our paradigm once with a weighted sum with α = 1 and β = 0, in order to obtain a solution tδ1 with the maximum possible diversity tδ1 [xδ], without regarding solution quality. This provides a relevant upper bound of the maximum diversity we may obtain. Thus, for each triplet (|X|,maxc, r ∈ { R, NR, S, NS }), we solve 420 problems. Then, Table 1 shows the average quality loss / (t2[xδ], t20[xδ]) / number of backtracks / percentage of optimal proofs for over 20 solution sets generated. All first solutions were proven to be optimal. The results show that using a ratio is the most robust approach, both in terms of optimality proof and number of backtracks. With respect to S and NS, t2 and t3 solutions are almost always obtained with a loss in quality, because this allows high increases in diversity and a better objective than with xQ = 0. Using a sum without normalization leads to a progressive removal of the quality criterion as the number of previous solutions increases. In a second experiment, we consider over-constrained instances. We augment the model with a set of boolean reified variables Y = {y1, y2, . . . , ync-1}, one-toone mapped with cost variables that represent violations, i.e., yi = (cost i > 0). Instead of considering diversity among the X variables, we consider Y. Diversity is applied on the overconstrained aspect of the instances, not on the values taken by variables. Table 2 shows the results for 20 solutions per generated set, with a 5 minute time-limit, using NS. We consider instances with and without the addition of an alternative notion of diversity, here represented by the FOCUS constraint. In the fourth column, FOCUS(costs, yc, |costs|, 0) is used. Quality loss is then represented by a variable x′Q = xQ + yc instead of xQ. As in Table 1, for each ratio we show: The average quality loss / (t2[xδ], t20[xδ]) / number of backtracks / percentage of optimal proofs for over 20 solution sets generated. Table 2 highlights that solution quality and diversity as well as the solving process are not strongly affected when our paradigm is used in the context of over-constrained problems or with alternative diversity notions.

2) TSPLIB. We used a graph-variable model [Fages and Lorca, 2012] for solving TSPLIB symmetric instances [Reinelt, 1991], which are state-of-the-art routing benchmarks. We used channeling constraints [Cheng et al., 1999] to make the link between the edges in the graph variable and boolean variables expressing whether a route takes the road between two cities or not, used as diversity variables.

Table 3 shows the results for instances such that the first optimal solution can be found and proved in less than one minute (without giving the optimum value as an upper-bound of the objective variable). We generated a total of 20 solutions per instance, defining a ratio (R) with L1 norm. For most instances, proof of optimality can be done in less than one minute for all solutions. If it is not the case for one solution, generally the other diverse solutions are not proved in under a one minute. The results show low average quality losses, which is interesting in practice for routing problems.

8 Conclusions and FutureWork

We have proposed a generic paradigm for producing diverse solutions of high quality in constraint-based optimization, which can be specialized to the context of over-constrained problems. We suggest considering diversity from additional points of view, based on concepts expressed by counting constraints. Future work includes using other counting constraints and implementation in an industrial context.