Restricciones que rompen la simetría - Symmetry-breaking constraints
En el campo de las matemáticas llamado optimización combinatoria , el método de las restricciones que rompen la simetría se puede utilizar para aprovechar las simetrías en muchos problemas de satisfacción y optimización de restricciones, agregando restricciones que eliminan las simetrías y reducen el tamaño del espacio de búsqueda.
Las simetrías en un problema combinatorio aumentan el tamaño del espacio de búsqueda y, por lo tanto, se pierde tiempo en visitar nuevas soluciones que son simétricas a las soluciones ya visitadas. El tiempo de solución de un problema combinatorio se puede reducir agregando nuevas restricciones, denominadas restricciones de ruptura de simetría, de modo que algunas de las soluciones simétricas se eliminen del espacio de búsqueda mientras se conserva la existencia de al menos una solución.
La simetría es común en muchos problemas combinatorios de la vida real. Por ejemplo, ciertos vehículos en el problema de rutas de vehículos pueden ser idénticos. Para un plan de enrutamiento válido, cada permutación de dichos vehículos idénticos produce otro plan de enrutamiento válido con el mismo valor de función objetivo.