Learning-Augmented Combinatorial Solvers: A Solver-Architecture Taxonomy

Abstract This paper presents a solver-architecture taxonomy of machine-learning and reinforcement-learning interventions in combinatorial solving. Rather than treating learning-augmented solving as a collection of isolated applications, we organize existing methods according to the solver-level decisions they influence, including propagation, branching, conflict analysis, restart control, structural analysis, and formulation-level reasoning. The discussion focuses on SAT/CDCL, Lazy Clause Generation, and related constraint-based, disjunctive, and graph-structured optimization frameworks, where learned models are increasingly used to guide decisions traditionally governed by handcrafted heuristics. We connect these intervention points to representative learning paradigms, including supervised prediction, reinforcement learning, graph neural networks, transformer-based encoders, and neuro-symbolic reasoning. The resulting taxonomy clarifies where learning can be integrated without compromising solver correctness, where empirical evidence remains limited, and where issues of generalization, interpretability, data generation, and runtime overhead remain open. The paper aims to provide a structured conceptual map for researchers developing hybrid symbolic--statistical solvers for hard combinatorial problems.