EUVIMEDEUVIMED entdecken
Crossref

Faster Symmetry Breaking Constraints for Abstract Structures

Özgür Akgün, Mun See Chang, Ian P. Gent, Christopher Jefferson

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14132-14139

DOI: 10.1609/aaai.v40i17.38425 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Özgür Akgün und 3 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In constraint programming and related paradigms, a modeller specifies their problem in a modelling language for a solver to search and return its solution(s). Using high-level modelling languages such as ESSENCE, a modeller may express their problems in terms of abstract structures. These are structures not natively supported by the solvers, and so they have to be transformed into or represented as other structures before solving. For example, nested sets are abstract structures, and they can be represented as matrices in constraint solvers. Many problems contain symmetries and one very common and highly successful technique used in constraint programming is to “break” symmetries, to avoid searching for symmetric solutions. This can speed up the solving process by many orders of magnitude. Most of these symmetry-breaking techniques involve placing some kind of ordering for the variables of the problem, and picking a particular member under the symmetries, usually the smallest. Unfortunately, applying this technique to abstract variables produces a very large number of complex constraints that perform poorly in practice. In this paper, we demonstrate a new incomplete method of breaking the symmetries of abstract structures by better exploiting their representations. We apply the method in breaking the symmetries arising from indistinguishable objects, a commonly occurring type of symmetry, and show that our method is faster than the previous methods proposed in (Akgün et al. 2025).

Zitieren

APA

Akgün, Ö., Chang, M. S., Gent, I. P., & Jefferson, C. (2026). Faster Symmetry Breaking Constraints for Abstract Structures. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14132-14139. https://doi.org/10.1609/aaai.v40i17.38425

Vancouver

Akgün Ö, Chang MS, Gent IP, Jefferson C. Faster Symmetry Breaking Constraints for Abstract Structures. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14132-14139. doi:10.1609/aaai.v40i17.38425

BibTeX
@article{Akgn2026,
  author = {Akgün, Özgür and Chang, Mun See and Gent, Ian P. and Jefferson, Christopher},
  title = {Faster Symmetry Breaking Constraints for Abstract Structures},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {17},
  pages = {14132--14139},
  doi = {10.1609/aaai.v40i17.38425}
}
Kostenlos starten →