Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Global Cut Framework for Removing Symmetries

Filippo FocacciContact Information and Michaela MilanoContact Information

(5)  ILOG S.A., 9 rue de Verdun, BP 85, F-94253 Gentilly, France
(6)  DEIS University of Bologna, V.le Risorgimento, 2, 40136, Italy
Abstract
In this paper, we propose a general technique for removing symmetries in CSPs during search. The idea is to record no-goods, during the exploration of the search tree, whose symmetric counterpart (if any) should be removed. The no-good, called Global Cut Seed (GCS), is used to generate Symmetry Removal Cuts (SRCs), i.e., constraints that are dynamically generated during search and hold in the entire search tree. The propagation of SRCs removes symmetric configurations with respect to already visited states. We present a general, correct and complete filtering algorithm for SRCs. The main advantages of the proposed approach are that it is not intrusive in the problem-dependent search strategy, treats symmetries in an additive way since GCSs are symmetry independent, and enables to write filtering algorithms which handle families of symmetries together. Finally, we show that many relevant previous approaches can be seen as special cases of our framework.

Contact Information Filippo Focacci
Email: ffocacci@ilog.fr

Contact Information Michaela Milano
Email: mmilano@deis.unibo.it
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Referenced by
2 newer articles

  1. Sabharwal, Ashish (2008) SymChaff: exploiting symmetry in a structure-aware satisfiability solver. Constraints
    [CrossRef]
  2. Cohen, David (2006) Symmetry Definitions for Constraint Satisfaction Problems. Constraints 11(2-3)
    [CrossRef]
Remote Address: 38.107.191.107 • Server: mpweb18
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)