Thesis:

Backbones in pseudo-boolean optimization: extraction and analysis

Backbone, the set of variables that are fixed across all optimal solutions, captures key structural properties of combinatorial optimization problems. The backbone provides interpretable indicators of problem hardness and, as demonstrated by recent research in SAT, valuable supervision targets for learning-based methods. Yet, the Pseudo-Boolean Optimization (PBO) domain has lacked dedicated tools for its extraction. Here, we introduce three new backbone extractors for Pseudo-Boolean Optimization (PBO): RoundingBack, a PBO-native extractor built on top of RoundingSAT; GuroBack, an extractor built on top of the MILP solver Gurobi; and NapBack, a pipeline that converts PBO instances into SAT using NaPS and delegates the backbone extraction to CadiBack, a backbone extractor for SAT. Additionally, we propose two heuristic variants of RoundingBack: RB-WP (weighted-propagation ordering) and RB-PG (diversity-driven phase guidance). Each extractor demonstrates distinct strengths tailored to different domain applications. On the PBO Competition 2024 OPT-Lin benchmark, RB-PG achieves the highest extraction coverage (223 of 335 instances, 67%), outperforming GuroBack and NapBack. Our experimental evaluation also shows that RoundingBack, GuroBack, and NapBack are complementary, and it is often the case that when an extractor fails, another is suitable. Beyond algorithmic performance, a large-scale analysis over more than eight thousand instances shows a bimodal distribution distinguishing flexible and rigid problem classes. We also show that the correlation between backbone density and problem hardness is domain-specific. All extracted backbones are publicly released to foster future research in learning-based PBO and structural instance analysis.