El trabajo de Martin Cooper propone una nueva metodología para la generación de desigualdades en problemas de optimización polinómica binaria
Martín Cooper, estudiante de Ingeniería UC, fue seleccionado como uno de los ocho finalistas del Undergraduate Operations Research Prize de INFORMS 2026, por su trabajo “Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization”.
La investigación fue desarrollada en el marco de un proyecto de investigación de pregrado (iPre), bajo la supervisión de la profesora del Departamento de Ingeniería Industrial y de Sistemas UC, Margarita Castro y como parte de su proyecto Fondecyt Regular 1261833.
El estudio aborda problemas de optimización polinómica binaria, una familia de problemas de optimización combinatoria que incluye, entre otros casos, el conocido problema Max-Cut.
Una nueva forma de generar desigualdades
Los problemas de optimización polinómica binaria pueden representarse mediante estructuras matemáticas llamadas hipergráficos, que permiten modelar interacciones entre más de dos elementos. Debido a la complejidad de estos problemas, encontrar soluciones de manera eficiente puede ser especialmente desafiante a medida que aumenta el tamaño de las instancias.
Una de las herramientas utilizadas para enfrentar esta dificultad son las desigualdades o cuts, que permiten fortalecer la formulación matemática de un problema y facilitar su resolución computacional. Tradicionalmente, estas desigualdades se han diseñado de manera específica para determinadas estructuras, como ciclos o flowers.
El trabajo de Martín Cooper propone una alternativa basada en Decision Diagrams (DDs), estructuras que permiten representar de manera compacta determinadas relaciones dentro del problema. A partir de un soporte o subestructura previamente seleccionada, el método construye un Decision Diagram capaz de generar automáticamente una desigualdad válida para esa estructura y luego incorporarla al problema original.
Además de desarrollar este mecanismo de generación de desigualdades, la investigación estudia las propiedades de los Decision Diagrams utilizados. Entre sus resultados teóricos se encuentran una representación compacta específica para estos problemas, una formulación extendida del conjunto factible y una caracterización del ancho de los diagramas mediante antichains válidos. El trabajo también establece condiciones que permiten certificar cuándo las desigualdades generadas corresponden a facetas del poliedro local.
Resultados computacionales
La metodología fue evaluada en dos conjuntos de problemas de referencia: LABS y VISION.
En LABS, una de las estrategias desarrolladas logró cerrar hasta un 92,4% de la brecha inicial de la relajación en el nodo raíz, utilizando las desigualdades generadas por el método.
En el conjunto VISION, una de las configuraciones logró cerrar el 100% de la brecha en el nodo raíz en las 45 instancias evaluadas. Además, alcanzó un tiempo promedio de resolución de 5,76 segundos, frente a los 71,79 segundos obtenidos por el procedimiento de referencia utilizado en el estudio.
Estos resultados muestran el potencial de los Decision Diagrams como herramienta para generar nuevas desigualdades de manera sistemática y contribuir a la resolución computacional de problemas de optimización combinatoria.
Presentación en San Francisco
Como finalista del Undergraduate Operations Research Prize, Martín Cooper presentará su investigación el próximo 1 de noviembre en el marco del INFORMS Annual Meeting 2026, que se realizará entre el 1 y el 4 de noviembre en San Francisco, Estados Unidos.
La presentación será también la instancia en que se dará a conocer al ganador del premio.