Thesis:

Backbone-based predict and search for pseudo-boolean optimization

This thesis investigates the integration of Machine Learning (ML) techniques to accelerate the solution of combinatorial optimization problems, focusing on instances formulated under the Pseudo-Boolean Optimization (PBO) paradigm. In PBO, constraints are expressed as linear inequalities over Boolean variables, and the objective function is defined as a linear combination of these variables. Although ML-based approaches have been increasingly applied to combinatorial optimization, their direct integration into solvers may introduce prediction errors that lead to infeasible solutions or degradation in solution quality. The Predict-and-Search (PaS) framework addresses this limitation by using ML predictions to generate additional constraints that reduce the search space before invoking the solver. However, existing PaS implementations have been primarily developed for Mixed Integer Linear Programming (MILP) and typically rely on heuristically generated labels derived from near-optimal solutions during training, thereby sacrificing optimality guarantees. This thesis introduces Backbone-based Predict and Search (BackPaS), a specialized adaptation of the PaS framework for PBO. The main contribution consists of redefining the prediction task as the identification of the backbone of an instance, defined as the set of variables whose assignments remain fixed across all optimal solutions. Correctly predicting these variables enables a reduction of the solver’s search space without compromising optimality(...).

Esta tesis aborda la integración de técnicas de aprendizaje automático (ML, Machine Learning) para acelerar la resolución de problemas combinatorios de optimización, específicamente aquellos formulados bajo el paradigma de Optimización Pseudo-Booleana (PBO, Pseudo-Boolean Optimization). En PBO, las restricciones se expresan como desigualdades lineales sobre variables booleanas, junto con una función objetivo también definida como combinación lineal de dichas variables. Si bien diversos enfoques de ML han sido aplicados a problemas combinatorios, su incorporación directa en solucionadores puede generar errores de predicción que conduzcan a soluciones infactibles o a una pérdida de calidad respecto del óptimo. El marco de trabajo Predict-and-Search (PaS) surge como una estrategia para mitigar estos problemas, utilizando predicciones de un modelo de ML para añadir restricciones adicionales que reducen el espacio de búsqueda antes de invocar el solucionador. No obstante, las implementaciones existentes de PaS han sido desarrolladas principalmente para Programación Entera Mixta (MILP, Mixed Integer Linear Programming) y suelen entrenar los modelos con etiquetas heurísticas derivadas de soluciones cercanas al óptimo, sacrificando garantías de optimalidad. En esta tesis se propone Backbone-based Predict and Search (BackPaS), una adaptación especializada del marco PaS al contexto de PBO. La contribución principal consiste en redefinir la tarea de predicción como la identificación del backbone de una instancia, entendido como el conjunto de variables cuya asignación permanece fija en todas las soluciones óptimas(...).