Extraction and prediction of backbones in pseudo-boolean problems

Abstract

The 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.