Resumen: En la programación de restricciones y paradigmas relacionados, un modelador especifica su problema en un lenguaje de modelado para que un solucionador busque y devuelva su(s) solución(es). Utilizando lenguajes de modelado de alto nivel como Essence, un modelador puede expresar sus problemas en términos de estructuras abstractas. Estas son estructuras que los solucionadores no admiten de forma nativa y, por lo tanto, deben transformarse o representarse como otras estructuras antes de resolverlas. Por ejemplo, los conjuntos anidados son estructuras abstractas y se pueden representar como matrices en solucionadores de restricciones. Muchos problemas contienen simetrías y una técnica muy común y de gran éxito utilizada en la programación de restricciones es “romper” las simetrías para evitar buscar soluciones simétricas. Esto puede acelerar el proceso de resolución en muchos órdenes de magnitud. La mayoría de estas técnicas de ruptura de simetría implican colocar algún tipo de orden para las variables del problema y elegir un miembro particular bajo las simetrías, generalmente el más pequeño. Desafortunadamente, aplicar esta técnica a variables abstractas produce una gran cantidad de restricciones complejas que funcionan mal en la práctica. En este artículo, demostramos un nuevo método incompleto para romper las simetrías de estructuras abstractas explotando mejor sus representaciones. Aplicamos el método para romper las simetrías que surgen de objetos indistinguibles, un tipo de simetría que ocurre comúnmente, y mostramos que nuestro método es más rápido que los métodos anteriores propuestos en (Akgün et al. 2025).
Publicado originalmente en export.arxiv.org el 17 de noviembre de 2025.
Ver fuente original
