Alvarado Ulloa, Bryan Jesús2026-10-142026-10-142024https://repositorio.usm.cl/handle/123456789/79464The challenge of identifying backbones in Pseudo-Boolean (PB) problems is addressed, where backbones are variables that maintain fixed values across all optimal solutions in optimization problems, or across all feasible solutions in decisional problems. A novel method for both extracting and predicting these backbones is introduced. The methodology involves a three-step pipeline: (1) converting PB instances into SAT problems, (2) using SAT solvers to extract the backbone, and (3) mapping the extracted backbone back to the original PB variables. Additionally, a predictive model based on Graph Neural Networks (GNNs) is developed to estimate the likelihood of variable membership in the backbone. Experimentalresultsdemonstratetheeffectivenessofthisapproach,highlighting its potential to uncover the underlying structure of PB problems and improve the efficiency of solving these complex optimization tasks.29 páginasenPseudo-Boolean optimizationBackbone extractionSAT solversGraph Neural NetworksVariable predictioninfo:eu-repo/semantics/openAccess3560902039801