Contributions to automatic configuration and selection for satisfiability

Resumen

En el área de las ciencas de la computación, es sabido que los algoritmos pueden exhibir comportamientos completamente diferentes dependiendo de como estén configurados sus parámetros, agudizándose este fenómeno cuando los problemas que se abordan son NP-Completos. Por ejemplo, se ha demostrado experimentalmente que configurar solvers para los problemas de la SATisfactibilidad (SAT), la Maxima SATisfactibilidad (MaxSAT) o la programación lineal de enteros mixta (MIP), puede resultar en mejoras de órdenes de magnitud. En esta tesis, mostramos cómo algoritmos metaheurísticos configurados de manera automática pueden resolver de forma eficiente diversas familias de instancias industriales y artificiales del problema MaxSAT. A continuación, nos centramos en mejorar el configurador automático de algoritmos GGA proporcionando un nuevo configurador distribuido que lo supera en varias familias de instancias industriales y artificiales de los problemas SAT y MIP. Finalmente, para hacer que esta tecnología sea más accesible para todas las comunidades científicas y la industria, presentamos la herramienta PyDGGA que implementa nuestro nuevo configurador. Además, presentamos el paquete OptiLog el cual permite la creación rápida de sistemas basados en SAT que adicionalmente incorpora un módulo de configuración automática para facilitar el uso de varias herramientas de configuración.