Thesis:

Probing features for automatic algorithm selection for pseudo-boolean optimization

For NP-hard problems like Pseudo-Boolean Optimization (PBO), solver performance varies dramatically across instances, making algorithm selection a critical bottleneck. Current Automatic Algorithm Selection (AAS) systems for PBO depend primarily on static problem features, ignoring crucial dynamic information. In contrast, AAS for Boolean Satisfiability (SAT) has demonstrated that "probing" features, gathered from short solver runs, are essential for making high-quality, time-sensitive predictions. This thesis addresses this gap by systematically integrating and evaluating probing features within AAS frameworks for PBO. The study investigates their effectiveness across multiple machine learning paradigms, including regression-based models, multiclass and multilabel classification approaches, and a novel hybrid framework that combines predictive and decision-oriented strategies. The outcome of this investigation is MetaPB, a new open-source meta-solver that leverages both static and probing features to improve solver selection performance. Extensive empirical evaluation on benchmark instances from the 2024 PBO Competition demonstrates that MetaPB consistently outperforms the best individual solver in the portfolio. Furthermore, despite relying exclusively on open-source(...).

Para problemas NP-hard como la Optimización Pseudo-Booleana (PBO), el rendimiento de los solvers varía drásticamente entre instancias, lo que convierte la selección de algoritmos en un cuello de botella crítico. Los sistemas actuales de Selección Automática de Algoritmos (AAS) para PBO dependen principalmente de características estáticas del problema, ignorando información dinámica crucial. En contraste, la AAS para Satisfacibilidad Booleana (SAT) ha demostrado que las características de dinámicas (probing), obtenidas a partir de ejecuciones cortas de los solvers, son esenciales para realizar predicciones de alta calidad y sensibles al tiempo. Esta tesis aborda esta brecha mediante la integración y evaluación sistemática de características de probing dentro de marcos de AAS para PBO. El estudio investiga su efectividad a través de múltiples paradigmas de aprendizaje automático, incluyendo modelos basados en regresión, enfoques de clasificación multiclase y multietiqueta, y un nuevo marco híbrido que combina estrategias predictivas y orientadas a la decisión. El resultado de esta investigación es MetaPB, un nuevo meta-solver de código abierto que aprovecha tanto características estáticas como de probing para mejorar el rendimiento en la selección de solvers. Una evaluación empírica exhaustiva sobre instancias de la Competencia PBO 2024 demuestra que MetaPB supera consistentemente al mejor solver individual del portafolio. Además, a pesar de basarse exclusivamente en solvers de código abierto(...).