Un estudio sobre la aproximación de búsqueda de aprendizaje en ramificación y acotación entera mixta: selección de nodos en SCIP
Autores: Yilmaz, Kaan; Yorke-Smith, Neil
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Un estudio sobre la aproximación de búsqueda de aprendizaje en ramificación y acotación entera mixta: selección de nodos en SCIP
Categoría
Ingeniería y Tecnología
Subcategoría
Inteligencia Artificial
Palabras clave
Aprendizaje automático
Selección de nodos
Programación entera mixta
Aprendizaje por imitación
Heurística
SCIP
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 25
Citaciones: Sin citaciones
En línea con la creciente tendencia de utilizar el aprendizaje automático para ayudar a resolver problemas de optimización combinatoria, una idea prometedora es mejorar la selección de nodos dentro de un árbol de ramificación y poda de programación entera mixta (MIP) mediante el uso de una política aprendida. El trabajo previo utilizando aprendizaje por imitación indica la viabilidad de adquirir una política de selección de nodos, aprendiendo un orden adaptativo de búsqueda de nodos. En contraste, nuestra política de aprendizaje por imitación se centra únicamente en aprender cuál de los hijos de un nodo seleccionar. Presentamos un método fuera de línea para aprender dicha política en dos configuraciones: una que comprende una heurística al comprometerse con la poda de nodos; una que es exacta y retrocede desde una hoja para garantizar encontrar la solución entera óptima. La primera configuración corresponde a un selector de hijos durante la inmersión, mientras que la última es similar a una heurística de buceo. Aplicamos la política dentro del popular solucionador de código abierto SCIP, en configuraciones heurísticas y exactas. Los resultados empíricos en cinco conjuntos de datos MIP indican que nuestra política de selección de nodos conduce a soluciones significativamente más rápidas que el precedente de vanguardia en la literatura. Aunque no superamos al selector de nodos de referencia de SCIP altamente optimizado en términos de tiempo de resolución en soluciones exactas, nuestras políticas heurísticas tienen una brecha de optimalidad consistentemente mejor que todos los baselines, si la precisión del modelo predictivo es suficiente. Además, los resultados también indican que, cuando se aplica un límite de tiempo, nuestro método heurístico encuentra mejores soluciones que todos los baselines en la mayoría de los problemas probados. Explicamos los resultados mostrando que las políticas aprendidas han imitado el punto de referencia de SCIP, pero sin la interrupción temprana de la inmersión de este último. Nuestra recomendación es que, a pesar de las claras mejoras sobre la literatura, este tipo de selector de hijos de MIP se ve mejor en un enfoque más amplio para utilizar el aprendizaje en las decisiones del árbol de ramificación y poda de MIP.
Descripción
En línea con la creciente tendencia de utilizar el aprendizaje automático para ayudar a resolver problemas de optimización combinatoria, una idea prometedora es mejorar la selección de nodos dentro de un árbol de ramificación y poda de programación entera mixta (MIP) mediante el uso de una política aprendida. El trabajo previo utilizando aprendizaje por imitación indica la viabilidad de adquirir una política de selección de nodos, aprendiendo un orden adaptativo de búsqueda de nodos. En contraste, nuestra política de aprendizaje por imitación se centra únicamente en aprender cuál de los hijos de un nodo seleccionar. Presentamos un método fuera de línea para aprender dicha política en dos configuraciones: una que comprende una heurística al comprometerse con la poda de nodos; una que es exacta y retrocede desde una hoja para garantizar encontrar la solución entera óptima. La primera configuración corresponde a un selector de hijos durante la inmersión, mientras que la última es similar a una heurística de buceo. Aplicamos la política dentro del popular solucionador de código abierto SCIP, en configuraciones heurísticas y exactas. Los resultados empíricos en cinco conjuntos de datos MIP indican que nuestra política de selección de nodos conduce a soluciones significativamente más rápidas que el precedente de vanguardia en la literatura. Aunque no superamos al selector de nodos de referencia de SCIP altamente optimizado en términos de tiempo de resolución en soluciones exactas, nuestras políticas heurísticas tienen una brecha de optimalidad consistentemente mejor que todos los baselines, si la precisión del modelo predictivo es suficiente. Además, los resultados también indican que, cuando se aplica un límite de tiempo, nuestro método heurístico encuentra mejores soluciones que todos los baselines en la mayoría de los problemas probados. Explicamos los resultados mostrando que las políticas aprendidas han imitado el punto de referencia de SCIP, pero sin la interrupción temprana de la inmersión de este último. Nuestra recomendación es que, a pesar de las claras mejoras sobre la literatura, este tipo de selector de hijos de MIP se ve mejor en un enfoque más amplio para utilizar el aprendizaje en las decisiones del árbol de ramificación y poda de MIP.