资源论文Static Symmetry Breaking with the Reflex Ordering

Static Symmetry Breaking with the Reflex Ordering

2019-11-22 | |  40 |   42 |   0
Abstract LexLeader, a state of the art static symmetry breaking method, adds a lex ordering constraint for each variable symmetry of the problem to select the lexicographically least solution. In practice, the same method can also be used for partial symmetry breaking by breaking only a given subset of symmetries. We propose a new total ordering, reflex, as basis of a new symmetry breaking constraint that collaborates well among themselves as well as with Precedence constraints, thereby breaking more composition symmetries in partial symmetry breaking. An efficient GAC filtering algorithm is presented for the reflex ordering constraint. We propose the ReflexLeader method, which is a variant of LexLeader using the reflex ordering instead, and give conditions when ReflexLeader is safe to combine with the Precedence and multiset ordering constraints. Extensive experimentations demonstrate empirically our claims and substantial advantages of the reflex ordering over the lex ordering in partial symmetry breaking.

上一篇:Linear Arithmetic Satisfiability Via Strategy Improvement

下一篇:A Clause Tableau Calculus for MaxSAT

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...

  • Rating-Boosted La...

    The performance of a recommendation system reli...