Schnellere Symmetrie‑Breaking‑Bedingungen für abstrakte Strukturen

In der Constraint‑Programmierung formulieren Modellierer ihre Probleme in hoch‑abstrakten Sprachen wie Essence. Dabei entstehen oft abstrakte Strukturen – etwa verschachtelte Mengen – die von den Solver‑Engines nicht direkt unterstützt werden und deshalb in andere Darstellungen, z. B. Matrizen, überführt werden müssen.

Viele dieser Probleme enthalten Symmetrien. Um die Suche drastisch zu beschleunigen, setzen Entwickler häufig Symmetrie‑Breaking‑Techniken ein, die eine bestimmte Ordnung der Variablen festlegen und einen „kleinsten“ Vertreter wählen. Für abstrakte Variablen führt diese Vorgehensweise jedoch zu einer großen Menge komplexer Constraints, die in der Praxis schlecht skalieren.

Die neue Studie präsentiert einen innovativen, unvollständigen Ansatz, der die Symmetrien abstrakter Strukturen gezielt nutzt, indem er deren Repräsentationen besser ausnutzt. Besonders bei der Symmetrie von ununterscheidbaren Objekten – einer häufigen Symmetrie‑Form – zeigt sich die Methode deutlich schneller als die bisher vorgeschlagenen Verfahren (Akgün et al. 2025).