Minion (solucionador)

Minion es una herramienta para resolver problemas de satisfacción . A diferencia de las herramientas de programación con restricciones , que requieren que los usuarios escriban programas en un lenguaje de programación tradicional como C++ , Java o Prolog , Minion toma un archivo de texto que especifica el problema y lo resuelve utilizando únicamente este. Esto simplifica enormemente el uso de Minion, aunque requiere mucha menos personalización.

Se ha demostrado que Minion es más rápido que los principales solucionadores de restricciones comerciales, incluido CPLEX (anteriormente IBM ILOG). ^{[ 1 ]}

Minion fue presentado en 2006 por investigadores de la Universidad de St Andrews como un solucionador “rápido y escalable” para instancias CSP grandes y difíciles. ^{[ 2 ]} El proyecto proporciona un lenguaje de entrada compacto y una implementación en C++ de baja sobrecarga orientada al rendimiento y la eficiencia de la memoria. ^{[ 3 ]}

Minion implementa una variedad de tipos de variables y restricciones comúnmente utilizadas en el modelado de CSP, además de heurísticas de búsqueda y soporte para optimización. La arquitectura del solucionador prioriza las estructuras de datos optimizadas para caché y los propagadores especializados. Cabe destacar que los desarrolladores adaptaron técnicas de literales observados de la resolución SAT para acelerar la propagación de restricciones para, entre otras, sumas booleanas, la restricción global de elementos y restricciones de tabla. ^{[ 4 ] [ 5 ]}

El enfoque de modelado se basa en un formato de texto plano (analizado por Minion) en lugar de incrustar modelos en un lenguaje de programación anfitrión. Esto reduce la sobrecarga y permite la experimentación rápida de "modelado y ejecución" para grandes conjuntos de datos de referencia. ^{[ 2 ]}

En la evaluación original sobre puntos de referencia estándar, los autores informaron que Minion a menudo se ejecutaba entre uno y dos órdenes de magnitud más rápido que los conjuntos de herramientas de última generación de la época (incluidos ILOG Solver y Gecode) en instancias grandes y difíciles, con ganancias menores —o ralentizaciones— en problemas más fáciles. ^{[ 2 ]} Investigaciones posteriores han utilizado Minion como solucionador de referencia en estudios empíricos y tareas de generación de pruebas, lo que refleja su adopción dentro de parte de la comunidad de programación con restricciones. ^{[ 6 ]}

Minion se ha aplicado en trabajos académicos sobre búsqueda combinatoria, planificación y generación de pruebas, y está disponible para otros entornos a través de adaptadores (por ejemplo, del lenguaje R). ^{[ 7 ]}

• Documentación de Minion
• Repositorio de Github