Improvements of Symmetry Breaking During Search

Improvements of Symmetry Breaking During Search

Zichen Zhu

Department of Computer Science and Engineering The Chinese University of Hong Kong Shatin, N.T., Hong Kong

zzhu@cse.cuhk.edu.hk

Abstract

Symmetries are common in many constraint problems. They can be broken statically or dynamically. The focus of this paper is the symmetry breaking during search (SBDS) method that adds conditional symmetry breaking constraints upon each backtracking during search. To trade completeness for efficiency, partial SBDS (ParSBDS) is proposed by posting only a subset of symmetries. We propose an adaptation method recursive SBDS (ReSBDS) of ParSBDS which extends ParSBDS to break more symmetry compositions. We observe that the symmetry breaking constraints added for each symmetry at a search node are nogoods and increasing. A global constraint (incNGs), which is logically equivalent to a set of increasing nogoods, is derived. To further trade pruning power for efficiency, we propose weak-nogood consistency (WNC) for nogoods and a lazy propagator for SBDS (and its variants) using watched literal technology. We further define generalized weak-incNGs consistency (GWIC) for a conjunction of increasing nogoods, and give a lazy propagator for incNGs.

Recursive SBDS

SBDS[Gent and Smith, 2000] leaves no symmetric solutions since all symmetries are given. For problems with exponential number of symmetries, direct use of SBDS is impractical [Gent and Smith, 2000]. To trade completeness for efficiency, partial SBDS (ParSBDS) is proposed by posting only a subset of symmetries [Petrie and Smith, 2003].

We prove that ParSBDS has the pitfall to leave more symmetric subtrees and solutions than the widely used static method LexLeader [Crawford et al., 1996] given the same subset of symmetries and the input-order variable and minimum (maximum) value heuristics. We propose Recursive SBDS (ReSBDS) [Lee and Zhu, 2014a] to circumvent the pitfall of ParSBDS. The main idea of ReSBDS is to add extra symmetry breaking constraints during search recursively to prune also symmetric nodes of some pruned subtrees. Thus, ReSBDS can break extra symmetry compositions. When given generators of interchangeable variables (values) according to a static search heuristic, ReSBDS is complete in eliminating the entire symmetry group. We propose further a light version of ReSBDS method (LReSBDS) [Lee and Zhu, 2014b], which has similar pruning power of ReSBDS but with a reduced overhead.

An Increasing-Nogoods Global Constraint

An overhead for SBDS and its variants is the addition of a large number of nogoods with weak pruning power. We observe that the symmetry breaking constraints added for each symmetry at a search node are nogoods that are semantically related. We propose the notion of increasing nogoods [Lee and Zhu, 2014b]. A global constraint (incNGs) [Lee and Zhu, 2014b], which is logically equivalent to a set of increasing nogoods, is derived. Thus we can maintain only one incNGs for each given symmetry. A polynomial time filtering algorithm for incNGs and also an incremental version are proposed.

Weak-Nogood Consistency

Nogoods are weak in pruning and maintaining GAC is not cost effective even when the two watched literal technique [Moskewicz et al., 2001] is utilized. We propose weaknogood consistency (WNC) [Lee and Zhu, 2015], a weaker consistency notion for nogoods to trade pruning power for efficiency. We propose an efficient lazy propagator to enforce WNC for SBDS (and its variants) using one watched literal [Lee and Zhu, 2015]. First, our propagator generates the watched literal (symmetric assignment) on demand. Second, the propagator is triggered lazily when the watched literal becomes true, and effects prunings only when all but the last assignment of the nogood is true.

A similar weaker consistency, generalized weak-incNGs consistency (GWIC) [Lee and Zhu, 2015], together with a lazy propagator is also proposed for the incNGs global constraint [Lee and Zhu, 2015]. GWIC on a conjunction is equivalent to WNC on individual nogoods. By exploiting the increasing property of the nogoods in incNGs, our lazy propagator watches also one assignment for each global constraint, and operates and benefits from a similar lazy principle.

Experimental Results

This section gives one experiment on Balanced Incomplete Block Design (BIBD) to break matrix symmetries (variable symmetries). A BIBD instance can be determined by its parameters (v, k, λ). We use the same model by Lee and Zhu [2014b]. We first solve the benchmarks using the efficient and widely used static method Doublelex [Flener et al., 2002], and also LexLeader to break a much larger subset of symmetries. We then report the results of two dynamic methods ParSBDS and LReSBDS. ReSBDS are discarded in the comparison since LReSBDS is substantially more efficient [Lee and Zhu, 2014b] than it. Each dynamic method would be implemented with the four propagators: GAC on each nogood (GAC), the filtering algorithm of incNGs given by Lee and Zhu [2014b] (incNGs), WNC on each nogood (WNC) and GWIC on each incNGs constraint (GWIC). ParSBDS is given any two rows or columns being permutable and the Cartesian products of these two subsets. LReSBDS and LexLeader are both given adjacent rows or columns being permutable and the Cartesian products of any two rows or columns being permutable.

All experiments are conducted using Gecode Solver 4.2.0 on Xeon E5620 2.4GHz processors with 7GB. In the table, #s denotes the number of solutions, #f denotes the number of failures and t denotes the runtimes. Since WNC and GWIC have the same pruning power, we show their solutions and failures together and use tW and tG to denote the runtime of WNC and GWIC respectively. The search time out limit is 1 hour. An entry with the symbol "-" indicates that memory is exhausted. The best results are highlighted in bold. We use input variable ordering and maximum value ordering. DoubleLex orders rows and columns decreasingly.

Table 1 shows the results. The solution and search tree size by using LReSBDSGAC are reduced to half compared with that of ParSBDSGAC. The time is improved 3.47 times on average. After introducing incNGs constraint, ParSBDS and LReSBDS are improved 8.54 and 3.76 times on runtimes on average respectively. For our lazy propagators, ParSBDSWNC and LReSBDSWNC run 16.67 and 4.07 times faster than ParSBDSGAC and LReSBDSGAC on average respectively. ParSBDSGWIC and LReSBDSGWIC run 1.90 and 1.34 times faster than ParSBDSincNGs and LReSBDSincNGs on average respectively. LReSBDSGWIC performs the best and runs 7.90 and 1.12 times faster than LexLeader and DoubleLex on average respectively. Dynamic method beats static method. The benefits of our proposed three improvements are thus demonstrated.

Future Work

For partial symmetry breaking, McDonald and Smith (2006) show there may be a point where the benefit in reducing search from adding more symmetries is out-weighed by the extra overhead. To find the optimum point which has the minimum total runtime, we do not only need to find the number of symmetries to post but also which subset to choose. It is worthwhile to find a good subset of symmetries to break for static and dynamic partial symmetry breaking methods.

McDonald and Smith (2006) have shown how dynamic methods are affected by variable and value heuristics in partial symmetry breaking. The ReSBDS and LReSBDS method are no exception. It is worthwhile to investigate the interaction between these partial methods and search heuristics.

Nogood learning is a general technique for improving backtracking search [Dechter, 1990]. We envision that the increasing-nogoods constraint and the weak-nogood consistency are applicable to other scenarios in CP and SAT, in addition to symmetry breaking.