Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):
J. Fichte, M. Hecher, S. Szeider:
"Breaking Symmetries with RootClique and LexTopSort";
Vortrag: CP 2020 - 26th International Conference - Principles and Practice of Constraint Programming,
Louvain-laNeuve, Belgium;
07.09.2020
- 11.09.2020; in: "Principles and Practice of Constraint Programming - 26th International Conference, {CP} 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings",
(2020),
S. 286
- 303.
Kurzfassung englisch:
Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (CP 2018) presented a robust and scalable method for finding optimal fractional hypertree decompositions, based on an encoding to SAT Modulo Theory (SMT). In this paper, we provide an in-depth study of two powerful symmetry breaking predicates that allow us to further speed up the SMT-based decomposition: RootClique fixes the root of the decomposition tree; LexTopSort fixes the elimination ordering with respect to an underlying DAG. We perform an extensive empirical evaluation of both symmetry-breaking predicates with respect to the primal graph (which is known in advance) and the induced graph (which is generated during the search).
Schlagworte:
Symmetry breaking Hypergraphs Elimination orderings SAT Modulo Theory
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-58475-7_17
Zugeordnete Projekte:
Projektleitung Stefan Woltran:
HYPAR
Projektleitung Stefan Woltran:
START
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.