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.
|
 |
Global Cut Framework for Removing Symmetries
| |
|
Global Cut Framework for Removing Symmetries
Filippo Focacci5 and Michaela Milano6 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|