Talks and Poster Presentations (with Proceedings-Entry):
J. Fichte, M. Hecher, S. Szeider:
"Breaking Symmetries with RootClique and LexTopSort";
Talk: CP 2020 - 26th International Conference - Principles and Practice of Constraint Programming,
Louvain-laNeuve, Belgium;
2020-09-07
- 2020-09-11; in: "Principles and Practice of Constraint Programming - 26th International Conference, {CP} 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings",
(2020),
286
- 303.
English abstract:
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).
Keywords:
Symmetry breaking Hypergraphs Elimination orderings SAT Modulo Theory
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/978-3-030-58475-7_17
Related Projects:
Project Head Stefan Woltran:
HYPAR
Project Head Stefan Woltran:
START
Created from the Publication Database of the Vienna University of Technology.