Automatic Dominance Breaking for a Class of Constraint Optimization Problems

1 Introduction

Dominance relations in Constraint Optimization Problems (COPs) describe relations between two assignments where one is known to be subordinate compared with another with respect to satisfiability and/or objective value. Once dominance relations are found in a COP, they can be used to speed up Branch and Bound (BnB) search [Ibaraki, 1977].

A wealth of research studies how to exploit dominance relations in practice. With sophisticated insights of the problem structure, one could either add dominance breaking constraints to exclude dominated assignments [Prestwich and Beck, 2004; Getoor et al., 1997] or augment the BnB search algorithm with dominance test [Monette et al., 2007; Aldowaisan, 2001; Korf, 2004]. Empirical evidence has shown that these problem-specific methods can dramatically reduce the search space and so speed up the solving process.

Dominance breaking is useful in solving COPs, but identification of dominance relations is non-trivial in general. Chu and Stuckey [2012] give the first generic method for identifying a class of dominance relations and generating dominance breaking constraints for COPs. While clever and interesting, the method calls for manual derivation of mappings and conditions, which is taxing for the mathematically uninclined. Mears and de la Banda [2015] automate the derivation process to a large extent, but their method still has to select symmetries manually. Also, they could generate only the same constraints as those reported in the literature.

Manual derivation of free form dominance breaking constraints requires deep understanding of the problems and sometimes even ingenuity. Our goal is to automate the process to make dominance breaking accessible to the nonexperts by restricting the form of the dominance breaking constraints to nogoods. We start by giving a general theory of dominance relations over constraints and specialize our attention to partial assignments, which can be interpreted as conjunctions of equality constraints. Theorems are given to identify the sufficient conditions of when an assignment constraint dominates another for COPs with objectives and constraints of certain useful forms. Negation of dominated partial assignments are dominance breaking nogoods. Most importantly, nogoods generation can be formulated mechanically as constraint satisfaction. By controlling the length and quantities of the nogoods, our method can tune the collective strengths of the generated nogoods and find pruning opportunities that are often neglected by manual methods. Experimentation on a diversified set of benchmarks confirms the practicality of our method, which compares favourably against manual methods both in efficiency and ease of use, and exhibits runtime (including both nogood generation and solving time) speed-up of up to three orders of magnitude.

2 Background

A Constraint Satisfaction Problem (CSP) P is a tuple (X,D,C) consisting of a finite set of variables X = {x1, . . . , xn}, a mapping D from variable x ∈ X to its finite domain D(x) and a set of constraints C, where each constraint c ∈ C is a subset of the Cartesian product D(xi1 ) × · · · × D(xik ) over the scope var(c) = {xi1 , . . . , xik } ⊆ X. A Constraint Optimiaztion Problem (COP) (X, D, C, f) extends a CSP with an objective function f .

An assignment x = v is an equational constraint which assigns a value v ∈ D(x) to variable x ∈ X. A partial assignment θ for variables X′ ⊆ X is the set of assignments {x = v|x ∈ X′ }, where X′ is the scope var(θ) of θ. A full assignment is a partial assignment when X′ = X. When the context is clear, we use θ to denote the tuple (vi1 , . . . , vil ), where ij < ij+1, xij ∈ X′ and |X′ | = l. The projection θ↓Y of θ onto Y ⊆ var(θ) is the partial assignment {x = v|(x = v) ∈ θ ∧ x ∈ Y }.

A full/partial assignment θ satisfies a constraint c iff θ↓var(c)∈ c, where var(c) ⊆ var(θ). A solution of a COP

P = (X,D,C, f) is a full assignment that satisfies all constraints in C, and P is satisfiable if the the set of all solutions sol(P) is not empty. In the remainder of the paper, we use ¯ θ to emphasize that it is a full assignment.

The objective function f maps every full assignment to a real number. Without loss of generality, the goal of solving a COP is to find an optimal solution ¯ θopt such that ¯ θopt is a solution of P and f(¯ θopt) ≤ f(¯ θ′ ) for any other solution ¯ θ′ of P. In other words, the objective function is minimized. (Remove) In constraint programming, The Branchand-bound (BnB) algorithm [Land and Doig, 1960] usually solves a COP by iteratively finding a solution with better objective value, and pruning subtrees that contain no better solution than the best solution found so far. The iterative process is repeated until no better solution can be found and the last solution is returned as the optimal solution.

Here we review some basic concepts in relational mathematics. A binary relation R over two sets S and S′ is a set of ordered pairs (s, s′ ) where s ∈ S and s′ ∈ S′ . If S = S′ , such a binary relation is homogeneous; otherwise it is heterogeneous. For a homogeneous relation R over S, R is transitive if ∀s, s′ , s′′ ∈ S, sRs′ ∧ s′Rs′′ ⇒ sRs′′ , and it is irreflexive if ∄s ∈ S such that sRs. The transitive closure of a homogeneous relation R on a set S is the smallest relation on S that contains R and is transitive. In our work, we slightly generalise the transitive closure to heterogeneous relation R : S ↦→ S′ by a two-step construction: (1) construct a relation ˆR over the union ˆ S = S ∪S′ such that ˆR = R as a set of ordered pairs, and 2) take the transitive closure ˆR+ of ˆR on the set ˆ S.

Let ΘP be the set of full assignments of a COP P = (X,D,C, f). A dominance relation ≺a with respect to P is a transitive and irreflexive relation such that for ¯ θ, ¯ θ′ ∈ ΘP if ¯ θ ≺a ¯ θ′ with respect to P, then either: 1) ¯ θ is a solution of P and ¯ θ′ is not a solution of P, or 2) both ¯ θ and ¯ θ′ are solutions of P and f(¯ θ) ≤ f(¯ θ′ ), or 3) both ¯ θ and ¯ θ′ are not solutions of P and f(¯ θ) ≤ f(¯ θ′ ). We say that ¯ θ dominates ¯ θ′ . The following theorem states that it is sound to prune all dominated full assignments.

Theorem 1. [Chu and Stuckey, 2012] Given a COP P = (X, D, C, f ) and a dominance relation ≺a with respect to P . We can prune all full assignments ¯ θ′ ∈ ΘP whenever ∃¯ θ ∈ ΘP such that ¯ θ ≺a ¯ θ′ , without changing the satisfiability or optimal value of P .

Note that a dominance relation should be both transitive and irreflexive. If P is satisfiable, then there is at least one optimal solution ¯ θopt of P that is not dominated by any other solutions. Consider a simple COP P with one variable x with domain {0, 1} and a constant objective function, where Both {x = 0} and {x = 1} are optimal solutions of P. Given a dominance relation ≺a with respect to P , either {x = 1} ≺a {x = 0} or {x = 0} ≺a {x = 1}, but not both. Otherwise, we will have {x = 1} ≺a {x = 1} due to the transitive property, but it violates the irreflexive property of ≺a.

3 Automatic Generation of Dominance Breaking Nogoods

This section gives an overview of our method. Different from other works in the literature where dominance relations are manually identified, our method can automate the process of identifying and exploiting dominance relations as follows:

1. Given the problem model of a COP P , we will first analyze the objective and constraints of P and build a generation model as a CSP mechanistically for identifying all dominance breaking constraints with respect to P .
2. When instance data is presented, all solutions of the generation model are searched, and each solution corresponds to a dominance breaking constraint, which is in the form of a nogood.
3. All generated nogoods are added to the problem model of P before solving.

The key step is to build the generation model automatically based on the problem model of P. In the rest of the paper, our focus is to show that, for a COP P, the constraints in the generation model can be obtained directly from constraints and objectives in P. The generation model can be obtained by using only one pass automatic analysis on the problem model of P.

To facilitate the presentation of our work, we will first present a general theory of dominance relations over constraints in Section 4. If a constraint c is dominated by some constraint c′ with respect to a COP P, the negation ¬c is a dominance breaking constraint for P. Further, we will show that it suffices to consider three conditions, namely irreflexivity, betterment and implied satisfaction, to establish the dominance relation between c and c′ . In Section 5, we will restrict our attention to dominance relations over assignment constraints. We will give concrete results on what constraints should be presented in the generation model for different objectives and constraints in the problem model. In Section 6, we will give the skeleton code for implementation.

4 Dominance Relations Between Constraints

Chu and Stuckey [2012] investigated dominance relations on full assignments and search nodes. It is straightforward to generalise it to dominance relations between constraints.

Given a COP P = (X,D,C, f). Let Θc denote the set of all full assignments satisfying c. Suppose there are two constraints c and c′ of the same scope X′ ⊆ X, we say c dominates c′ , i.e. c ≺ c′ , with respect to P if ∀¯ θ′ ∈ Θc′ , ∃¯ θ ∈ Θc, such that ¯ θ ≺a ¯ θ′ for some dominance relation ≺a with respect to P. Note that we do not require c, c′ ∈ C. The following theorem is a direct consequence of Theorem 1.

Theorem 2. Given a COP P = (X,D,C, f) and two constraints c and c′ over X′ ⊆ X. If c ≺ c′ with respect to P, then P has the same satisfiability or optimal value as P ′ = (X, D, C ∪ {¬c′ }, f )

Proof. ∀¯ θ′ ∈ Θc′ , ∃¯ θ ∈ Θc s.t. ¯ θ ≺a ¯ θ′ . By Theorem 1, we can prune all dominated full assignments in Θc′ by adding ¬c′ to the constraint set C of P.

Once we could establish c ≺ c′ with respect to P, the negation of c′ is the desired dominance breaking constraint. To check c ≺ c′ , we can simply compare all solutions in Θc against those in Θc′ , but this is impractical. We give a sufficient condition for c ≺ c′ .

Theorem 3. Given a COP P = (X,D,C, f) and two constraints c and c′ over X′ ⊆ X. If there exists a bijective mapping σ : Θc ↦→Θc′ such that:

• irreflexivity: the transitive closure of σ is irreflexive
• betterment: ∀¯ θ ∈ Θc, f(¯ θ) ≤ f (σ(¯ θ))
• implied satisfaction: ∀¯ θ ∈ Θc, σ(¯ θ) is a solution of P implies ¯ θ is a solution of P

then c ≺ c′ .

Proof. (Sketch) We need to show that ∀¯ θ′ ∈ Θc′ , ∃¯ θ ∈ Θc such that ¯ θ ≺a ¯ θ′ where ≺a is a dominance relation with respect to P. The idea is similar to the proof of Theorem 3 by Chu and Stuckey [2012], based on which we show the transitive closure of σ is indeed a dominance relation ≺a.

We further prove that ∀¯ θ′ ∈ Θc′ , ∃¯ θ ∈ Θc such that ¯ θ ≺a ¯ θ′ with respect to P. Note that σ is a bijective mapping, so ∀¯ θ′ ∈ Θc′ , ∃σ-1 (¯ θ′ ) ∈ Θc. Since ≺a is constructed by taking the transitive closure of σ, σ-1 (¯ θ′ ) ≺a ¯ θ′ . Hence, c ≺ c′ .

From now on, when the context is clear, we use ≺ to denote a dominance relation between full assignments or constraints. To generate dominance breaking constraints, it remains to construct an appropriate σ for the purpose. In the following section, we show that this is possible for certain classes of objectives and constraints in the COP by limiting our attention to dominance relation between assignment constraints.

5 Dominance and Assignment Constraints

The bijective mapping in Theorem 3 needs to satisfy the irreflexivity, betterment and implied satisfaction conditions. Fulfilling irreflexivity turns out to be simple.

Theorem 4. Given a COP P = (X,D, C, f), and two constraints c and c′ over X′ ⊆ X. If Θc ∩Θc′ = ∅, all mappings σ : Θc ↦→Θc′ and their transitive closures are irreflexive.

Proof. Since Θc ∩Θc′ = ∅, θ ̸= θ′∀(θ, θ′ ) ∈ σ. If (¯ θ, ¯ θ′ ) ∈ σ, then (¯ θ′ , ∗) /∈ σ where ∗ is any full assignment. Thus, the transitive closure of σ is also irreflexive.

Fulfilling betterment and implied satisfaction for general constraints is difficult, but we consider a special class of constraints which arises out of partial assignments. A partial assignment θ with scope F is technically not a constraint, but essentially a set of equations, the conjunction of which, i.e. ∧e∈θ (e), can be interpreted as a constraint. We call it an assignment constraint. To avoid confusion in notation, we use AC(θ) to denote an assignment constraint for the partial assignment θ. The scope of AC(θ) is also F, and the length is |F|. We are interested in the conditions when an assignment constraint AC(θ) dominates another AC(θ′ ) with the same scope. Note that ¬AC(θ′ ) is in the form of a nogood [Katsirelos and Bacchus, 2005]. We call it a dominance breaking nogood with respect to P .

If θ ̸= θ′ , then ΘAC(θ) ∩ΘAC(θ′ ) = ∅ and irreflexivity in Theorem 3 holds. What remains is to find a bijective mapping σ that satisfies betterment and implied satisfaction.

Suppose there are two assignment constraints AC(θ) and AC(θ′ ) with the same scope F ⊆ X. We define the mutation mapping as σm : ΘAC(θ) ↦→ ΘAC(θ′ ), which maps a full assignment ¯ θ ∈ ΘAC(θ) to σm(¯ θ) ∈ ΘAC(θ′ ) such that σm(¯ θ) = (¯ θ\θ) ∪ θ′ . We note that every full assignment ¯ θ ∈ ΘAC(θ) has the form ¯ θ = θ∪{x = v|x ̸∈ F ∧v ∈ D(x)}. Thus, σm(¯ θ) = θ′ ∪ {x = v|x ̸∈ F ∧ v ∈ D(x)}, which "mutates" the θ component of ¯ θ to become θ′ . The following proposition shall be useful in our later discussion.

Proposition 1. Given a mutation mapping σm : ΘAC(θ) ↦→ ΘAC(θ′ ). ∀¯ θ ∈ ΘAC(θ), ¯ θ\θ = σm(¯ θ)\θ′ .

In the following, we give sufficient conditions for different classes of objectives and constraints to fulfill betterment and implied satisfaction. Unless otherwise stated, all formal results in the remainder of this section are given with the following context: given a COP P = (X,D, C, f) and two partial assignments θ and θ′ with the same scope F and the associated mutation mapping σm : ΘAC(θ) ↦→ ΘAC(θ′ ).

5.1 The Betterment Condition

Now we show the sufficient conditions for betterment hold for σm, namely ∀¯ θ ∈ ΘAC(θ), f(¯ θ) ≤ f(σm(¯ θ)). The key idea is to define the projection f↓var(θ) of f onto var(θ) so that the relative magnitude of f(¯ θ) and f(σm(¯ θ)) can be determined. In the following, we consider two types of objectives: separable and supermodular/submodular functions.

Separable Objectives

A function f is separable if it can be written as a linear combination of functions of individual variables, i.e. for a full assignment ¯ θ = (v1, . . . , vn), f(θ) = f1(v1) + · · · + fn(vn), where each component is fi : Z ↦→ R. For a partial assignment θ, we define f ↓var(θ) (θ) = fi1 (vi1 ) + · · · + fil (vil ) where (xij = vij ) ∈ θ for j = 1, . . . , l.

Theorem 5. Suppose the objective f is a separable function. If f↓F(θ) ≤ f↓F(θ′ ), then ∀¯ θ ∈ ΘAC(θ), f(¯ θ) ≤ f (σm(¯ θ)).

Proof. Suppose ¯ θ = (v1, . . . , vn) ∈ ΘAC(θ) and σm(¯ θ) = (v′1 , . . . , v′n ), then we have

by grouping the terms. By Proposition 1, ¯ θ\θ = σm(¯ θ)\θ′ , and ∑xij /∈F fij (vij ) = ∑xij /∈F fij (v′ij ). Thus f(¯ θ) ≤ f (σm( ¯ θ)) ⇐⇒ f↓F(θ) ≤ f↓F(θ′ ).

A typical example of separable functions is the linear function f(θ) = ∑i wivi, where wi ∈ R.

Supermodular and Submodular Objectives

A supermodular function is a set function g : 2V ↦→ R that assigns each subset S ⊆ V a value g(S) ∈ R such that

for every S, S′ ⊆ V with S ⊆ S′ and T ⊆ V \S′ . We could treat a supermodular function as an objective in a binary COP P = (X, D, C, f ) where ∀x ∈ X, D(x) = {0, 1}. A full assignment ¯ θ can be associated with a set S(¯ θ) = {i|(xi = 1) ∈ ¯ θ}, and we say f is equivalent to a supermodular function g if f(¯ θ) = g(S(¯ θ)). Similarly for a partial assignment θ, S(θ) = {i|(xi = 1) ∈ θ}, and we define f↓var(θ)(θ) = g(S(θ))

Theorem 6. Suppose the objective f is equivalent to a supermodular function g. If f↓F(θ) ≤ f↓F(θ′ ) and S(θ) ⊆ S(θ′ ), then ∀¯ θ ∈ ΘAC(θ), f(¯ θ) ≤ f (σm(¯ θ)).

Proof. Since g is a supermodular,

for S(θ) ⊆ S(θ′ ) ⊆ V = {1, . . . , n} and any set T ⊆ V \S(θ′ ). For a full assignment ¯ θ ∈ ΘAC(θ), we let T = {i|(xi = 1) ∈ ¯ θ ∧ xi /∈ F}. Since ¯ θ = θ ∪ {x = v|x /∈ F ∧ v ∈ D(x)}, we have f(¯ θ) = g(S(θ) ∪ T ). Furthermore, since ¯ θ′ = σm(¯ θ) = (¯ θ\θ) ∪ θ′ , f(¯ θ′ ) = g(S(θ′ ) ∪ T ). Then

Since f↓F (θ) ≤ f↓F (θ′ ), the above inequality implies that f(¯ θ) ≤ f(¯ θ′ ).

A function g is submodular if -g is supermodular. Thus minimizing a supermodular function is equivalent to maximizing a submodular function. We note that Theorems 3 and 6 (and also Theorem 5) can be easily adapted for maximization problems. Linear functions are also examples of submodular functions. Another typical example is the cut function in a graph with non-negative weights on edges.

5.2 The Implied Satisfaction Condition

Now we consider the implied satisfaction condition in Theorem 3. We give sufficient conditions for when ∀¯ θ ∈ ΘAC(θ), σm(¯ θ) ∈ sol(P) implies ¯ θ ∈ sol(P). Note that a full assignment ¯ θ ∈ sol(P) if ¯ θ satisfies all c ∈ C. It suffices to consider each constraint c separately.

We say a partial assignment θ is applied to c ∈ C by replacing every occurrence of x in c by value v for all (x = v) ∈ θ where x ∈ var(c) ∩ var(θ). The resulting constraint cθ has scope var(c)\var(θ). The following proposition is useful to prove implied satisfaction for various constraints in later subsections.

Proposition 2. ∀¯ θ ∈ ΘAC(θ) and a constraint c ∈ C, if cθ′ ⇒ cθ, then σm(¯ θ) satisfies c ⇒ ¯ θ satisfies c.

Proof. By Proposition 1, let β = ¯ θ\θ = σm(¯ θ)\θ′ . Since cθ′ ⇒ cθ, cθ′ ⊆ cθ. Thus, β satisfies cθ′ ⇒ β satisfies cθ, which means σm(¯ θ) satisfies c ⇒ ¯ θ satisfies c.

The types of constraints we will study include domain constraints, linear inequalities, Boolean disjunctions and the alldifferent and alldifferent except 0 constraints.

Domain Constraints

A domain constraint c = (x ∈ D(x)) is a unary constraint which restricts a variable x to take values from a set D(x). The condition for implied satisfaction is straightforward.

Theorem 7. Given a domain constraint c = (x ∈ D(x)) and a full assignment ¯ θ ∈ ΘAC(θ). If either (a) x /∈ F or (b) (x ∈ F) and v ∈ D(x) for some (x = v) ∈ θ, then cθ implies cθ′ .

Proof. Suppose x /∈ F. Then cθ = c = cθ′ , which means σm( ¯ θ) satisfies c iff ¯ θ satisfies c. Suppose x ∈ F and v ∈ D(x) for some (x = v) ∈ θ. In this case, cθ is always true. Thus ∀¯ θ ∈ ΘAC(θ), ¯ θ always satisfies c.

Linear Inequality Constraints

A linear inequality constraint has the form c = (∑ wixi ≤ b) where wi, b ∈ R. The sufficient condition for implied satisfaction is stated as follows.

Theorem 8. Given a linear inequality constraint c = (∑ wixi ≤ b). If e ≤ e′ where e = ∑(xi=vi)∈θ wivi and e′ = ∑(xi=v′i )∈θ′ wiv′i , then cθ′ implies cθ.

Boolean Disjunctions

The Boolean disjunction constraint ∨x∈Sx requires at least one Boolean variable x ∈ S takes the true value.

Theorem 9. Given a Boolean disjunction constraint c = (∨xi). If e′ implies e where e = ∨(xi=vi)∈θvi and e′ = ∨(xi=v′i )∈θ′v′i , then cθ′ implies cθ.

The proof idea is similar to that of Theorem 8.

Alldifferent and Alldifferent except 0 Constraints

The alldifferent constraint [R´egin, 1994] enforces that all variables in a set S take distinct values.

We say a partial assignment θ has no duplicated values if ∀e, e′ ∈ θ where e = (xi = vi), e′ = (xi′ = vi′), vi ̸= vi′ . The sufficient condition for implied satisfaction requires the set of assigned values to variables in S to be the same.

Theorem 10. Given a constraint c = alldifferent(S) where S ⊆ X. Let V = {v|(x = v) ∈ θ ∧ x ∈ F ′ } and V ′ = {v′ |(x = v′ ) ∈ θ′ ∧ x ∈ F ′ } where F ′ = F ∩ var(c). If V = V ′ and both θ and θ′ have no duplicated values, then cθ′ implies cθ.

Proof. The alldifferent constraint can be expressed as c = alldifferent({x|x ∈ var(c)\F} ∪ {x|x ∈ var(c) ∩ F}). Since V = V ′ ,

The alldifferent except 0 constraint [Beldiceanu et al., 2010] is a special case of the alldifferent constraint where all variables in a set S are required to take distinct values except for those variables that are assigned value 0. We say a partial assignment θ has no duplicated values except 0 if ∀(xi = vi), (xi′ = vi′) ∈ θ such that v ̸= vi′ ∨ v = 0 ∨ vi′ = 0. The sufficient condition is also related to the set of assigned values of θ and θ′ to variables in S.

Theorem 11. Given c = alldifferent except 0(S) where S ⊆ X. Let V = {v|(x = v) ∈ θ ∧ x ∈ F ′ ∧ v ̸= 0} and V ′ = {v′ |(x = v′ ) ∈ θ′ ∧ x ∈ F ′ ∧ v′ ̸= 0} where F ′ = F ∩ var(c). If both θ and θ′ have no duplicate values except 0 and V ⊆ V ′ , then cθ′ implies cθ.

The proof idea is similar to that of Theorem 10.

5.3 Compatibility between Dominance Nogoods

So far we only consider the soundness of the generated dominance nogoods for a COP P . When all generated dominance breaking nogoods are added to P , we need to ensure that not all optimal solutions are eliminated. We now show a sufficient condition for preservation of the optimal value of P .

Given two partial assignments θ = (vi1 , . . . , vil ) and θ′ = (v′i1 , . . . , v′il ) with the same scope F , we say θ is lexicographically smaller than θ′ , denoted as θ <lex θ′ , if there exists xij ∈ F such that vij < v′ij and vij′ = v′ij′ ∀j ′ < j. We say θ surpasses θ′ if either (a) f ↓var(θ) (θ) < f ↓var(θ′ ) (θ′ ) or (b) f↓var(θ)(θ) = f↓var(θ′ )(θ′ ) ∧ θ <lex θ′ . Note that the lexicographical ordering is a total order. The following theorem states that it is sufficient to enforce the condition that θ surpasses θ′ so that adding all identified dominance breaking nogoods ¬AC(θ′ ) to P will not change the satisfiability or optimal value.

Theorem 12. Given f is either a separable or supermodular function. If AC(θ) ≺ AC(θ′ ) and θ surpasses θ′ , the lexicographically smallest optimal solution satisfies ¬AC(θ′ ).

Proof. Suppose f↓var(θ)(θ) < f↓var(θ′ )(θ′ ). We claim that any solution satisfying AC(θ′ ) is not optimal.

• If f is separable, then

Since ¯ θ′ \θ′ = ¯ θ\θ, any solution satisfying AC(θ′ ) cannot be optimal since

• If f is supermodular, by theorem 6 we have S(θ) ⊆ S(θ′ ). So,

Thus, an optimal solution will not satisfy AC(θ′ ) if f↓var(θ) (θ) < f↓var(θ′ )(θ′ ).

Otherwise, suppose f ↓var(θ) (θ) = f ↓var(θ′ ) (θ′ ) and θ <lex θ′ . Let ¯ θ′ ∈ ΘAC(θ′ ) be an optimal solution of P. Since θ <lex θ′ and ¯ θ\θ = ¯ θ′ \θ′ , σ-1 m (¯ θ′ ) <lex ¯ θ′ . That is, if an optimal solution ¯ θ′ satisfiesΘAC(θ′ ), theremust be another optimal solution σ-1 m (¯ θ′ ) which is lexicographically smaller than ¯ θ′ . By contrapositive, the lexicographically smallest optimal solution cannot satisfy AC(θ′ ).

6 Dominance Nogood Generation

Given a length l. Using results in Section 5, we can check if an assignment constraint AC(θ) dominates another AC(θ′ ) with the same scope. Once this is established, ¬AC(θ′ ) can be added to P for dominance breaking. Note that we can generate dominance breaking nogoods for all COPs containing objectives and constraints listed in Section 5.

First we would like to consider the number of such pairs of assignment constraints.

Theorem 13. Given a COP P = (X,D, C, f) and a length l ≤ |X|. Suppose max(|D(xi)|) = d for xi ∈ X. There are O((|X| l ) · (dl 2 )) pairs of assignment constraints AC(θ) and AC(θ′ ) where θ ̸= θ′ and var(θ) = var(θ′ ) = F , |F | = l.

Proof. The candidate pairs can be enumerated by first selecting l variables xi1 , . . . , xil from X. And then we select two distinct tuples from D(xi1 ) × · · · × D(xil ), which has (∏k=1,...,l |D(xik )| 2 ) ≤ (dl 2 ) ways in total. Hence, there are totally O((|X| l ) · (dl 2 )) such candidate pairs.

Using the simple generate-and-test method to find and compare all possible pairs of partial assignments is inefficient. We note that sufficient conditions for betterment in Theorems 5 and 6, and those for implied satisfaction in Theorems 7 to 11 are nothing but constraints on the desired pairs of partial assignments. Thus, we model dominance nogood generation as constraint satisfaction problems.

1 int: n; int: l; int: d; 2 array [1..l] of var 1..n: F; 3 array [1..l] of var 1..d: v1; 4 array [1..l] of var 1..d: v2; 5 constraint increasing(F); 6 7 % betterment 8 ... 9 % implied satisfaction 10 ... 11 % compatibility 12 ...

The above code template shows our basic nogood generation model in MiniZinc [Nethercote et al., 2007]. Given a COP P = (X,D,C, f). We assume that |X| = n and d = max(|D(xi)|) for xi ∈ X. Note that the desired pairs of partial assignments θ and θ′ have the same scope. We use an array F to represent the common index set of variables in the scope. We also use v1 and v2 to represent the assigned values in θ and θ′ respectively. Thus, if ∃i ∈ {1, . . . , l} such that F[i] = k, v1[i] = t1 and v2[i] = t2, then (xk = t1) ∈ θ and (xk = t2) ∈ θ′ . Note that there are variable symmetries in the array F, and we break the symmetries by enforcing F [i] < F [i + 1] for all i = 1, . . . , l - 1.

With the stated variables, one can post constraints for betterment, implied satisfaction and compatibility according to the objective f and constraints c ∈ C. Using Theorems 4 to 12, each constraint/objective of the problem model P corresponds to O(1) constraints in the generation model in MiniZinc. Such a model can be generated mechanically by analyzing the problem model in only one pass in negligible time as compared to nogood generation and model solving time.

7 Experimental Evaluation

In this section, we present experimental results to demonstrate empirically the effectiveness of the generated dominance nogoods. We use MiniZinc 2.2.3 [Nethercote et al., 2007] to model both the problems and nogood generation respectively, and the back-end solver is Chuffed [Ohrimenko et al., 2009] 1 . Our experiments use four benchmarks, 10 instances for each problem configuration.

• The 0-1 knapsack problem (KP) is a classical combinatorial optimization problem with a linear objective and a linear inequality constraint. We use instances from https://people.eng.unimelb.edu.au/ pstuckey/dom-jump/ where the number of items n = 100, 150, 200, 250, 300.
• The Disjunctively constrained knapsack problem (DCKP) [Yamada et al., 2002] extends KP so that some pairs of items cannot be selected simultaneously. The extra condition can be modeled as a Boolean disjunction. For each instance of KP with n items, we augment the instance by randomly picking ⌊ηn(n - 1)/2⌋ incompatible pairs of items where η = 0.002.
• The Capacitated Concert Hall Scheduling Problem (CHSP) [Gange and Stuckey, 2018] is to schedule a set A of applications to a set H of concert halls. Each application a ∈ A has a period [sa, ea], an offered price pa and a requirement ra, and each concert hall h ∈ H has a capacity ch. The problem is to maximize a separable function with domain and alldifferent except 0 constraints. For n = 20, 25, 30, 35, 40, we generate random instances with 10 halls and n applications, 1 ≤ sa ≤ ea ≤ 100, 200 ≤ ra, ch ≤ 1000 and 10 ≤ pa ea-sa+1 . To demonstrate the effectiveness of our methods on harder instances, we present only instances which cannot be solved by the model with manual dominance breaking constraints within 60 seconds.
• The Weighted Maximum Cut Problem (WMCP) is a submodular maximization problem to find a partition (S, ¯ S) of vertices in a weighted undirected graph. For n ∈ {35, 40, 45, 50}, we generate random graphs with n vertices by independently sampling each edge with probability p = 0.1 whose weights are random integers in

1 All models and experimental data are available at https://github. com/AllenZzw/Automatic-Dominance-Breaking.

[1, 10]. As far as we know, no manual dominance breaking constraints exist for this problem, and we omit such a model in the experiments.

The problem models, the manual dominance breaking constraints, and the search strategies are from the literature.

We compare our method against the basic problem model (no-dom), and the model with manual dominance breaking constraints [Chu and Stuckey, 2012; Gange and Stuckey, 2018] (manual). We attempt to generate and augment the basic models with all nogoods of length up to 2 (2-dom), 3 (3-dom) and 4 (4-dom), but subjecting to a uniform timeout limit of 3600s for all benchmark instances.

Figures 1(a) to 1(d) show the average solving (blue solid bar) and dominance nogood generation time (red diagonal hatch bar) in log scale. The red bars (generation time) is stacked on the blue ones (solving time). Note that the ratio of the bars does not reflect time percentage. The generation time should not be read directly as the length of the red bars, but should be the difference of the total time and the solving time.

We first compare the problem solving time of our method against no-dom and manual to understand the strength of our generated dominance breaking nogoods. The five bars for each problem configuration correspond to the time for manual, no-dom, 2-dom, 3-dom and 4-dom respectively (except for WMCP where we omit manual). It is clear that the generated dominance breaking constraints can drastically reduce the solving time for all benchmarks. In KP and DCKP, nodom timeouts in all testing instances, while our method can reduce the solving time to within 10 minutes even for the largest instances. If we choose to compare against the timeout limit, then our method is 17142.6 and 19999.6 times faster than no-dom respectively. The speed-up of our method over no-dom is up to 125.7 times for CHSP, and up to 10.0 times for WMCP.

Comparing against manual, our method is always more efficient. In particular, our method is up to 1475.0 times faster than that of manual for KP, and the improvements for DCKP and CHSP are up to 2568.5 times and 115.4 times respectively. In general, 3-dom is always better than 2-dom. When the nogoods of 4-dom cannot be completely generated within the timeout limit, the comparison of the solving efficiency between 3-dom and 4-dom is inconclusive.

We also compare the total time (solving time + generation time) of our method with the solving time of no-dom and manual. Obviously, more time is needed to generate more nogoods. There is a trade-off between between stronger pruning and generation time. Still, our method comes out on top with 3-dom being the best. For KP, the speed-up is up to 4444.4 times compared with no-dom (timeout limit), and 12.5 times compared with manual. Similarly for DCKP, our method is faster than no-dom and manual by up to 665.4 times and 38.1 times respectively. As for CHSP, our method runs up to 142.2 and 102.0 times faster than both no-dom and manual respectively. For WMCP, our method is up to 7.0 times faster than no-dom.

We note that the solving time for many instances exceed the timeout limit, especially for no-dom and manual, and the actual acceleration of generated nogoods can be even higher.

Figures 2(a) to 2(d) compare different methods by showing the number of solved instances versus the running time for each benchmark. For both KP and DCKP, 3-dom can solve all instances within 10 minutes and 50 minutes respectively, and is better than all other methods, while no-dom times out on all instances. In addition, manual solves only around 30 and 20 instances out of 50 for KP and DCKP respectively. For CHSP, no-dom and manual can solve at most 38 instances out of 50, while all these instances can be solved by our method within 10 minutes. As for WCMP, the performance of 4-dom is the best among all solving methods. no-dom can only solve 32 instances out of 40, while 4-dom can solve 39.

While we do not show pruning strength in the graphs, 3dom and 4-dom all prune substantially more than manual. In other words, our method is able to generate dominance breaking nogoods that have not been discovered by manual derivation methods.

8 Concluding Remarks

Automatic generation of dominance breaking constraints is made possible by focusing on nogoods. Our theorems on sufficient conditions enable us to formulate nogood generation effectively as constraint satisfaction. An important advantage is the ability to control the strength of the generated nogoods. Our method discovers dominance breaking nogoods that had not been discovered before. The method can also be easily integrated into existing constraint modeling systems or solvers. There are several future research directions. A limitation of our method is that the nogoods are generated instance by instance, and the benefit of the dominance nogoods may not compensate the overhead for generation. One possibility is to improve the efficiency of nogood generation in general. Another limitaion is that our method can only be applied when the objective and all constraints in the problem can be analysed for betterment and implied satisfaction. We also expect similar results to be proven for other objectives and constraints, especially for global constraints with some sort of monotonic behavior.

Acknowledgments

We are grateful to the anonymous referees of IJCAI-20 for their useful comments and suggestions.