We present a GPU-CPU hybrid framework for Weighted Partial MaxSAT (WPMAX-SAT) that complements state-of-the-art CPU solvers with differentiable GPU optimization. The GPU stage directly optimizes instance-specific categorical decision parameters without a training dataset or a pretrained predictive model. The central challenge in extending differentiable optimization to WPMAX-SAT is the hard/soft clause asymmetry: hard clauses represent inviolable feasibility constraints while soft clauses carry weights. We introduce a hierarchical differentiable loss that prioritizes hard clause satisfaction before optimizing the weighted soft objective, ensuring that GPU gradient descent leans towards the constraint structure of WPMAX-SAT. Our framework transforms the GPU-optimized variable logits to high-confidence assignments and transfers them to CPU solvers via two complementary modes: partial guidance, which injects the most confident perturbed partial variable assignments as soft clauses into N parallel solver instances, and phase initialization, which guides the CDCL solver's internal branching polarity with the full GPU assignment as a warm start to preserve the problem's originality. We evaluate on all 229 instances of the MSE 2024 (most recent due to cancellation in 2025) anytime weighted benchmark with the top 2 winners as baselines; our hybrid framework improves the average solution score by up to 4.9% over tt-open-wbo-inc-Glucose and 4.8% over SPB-MaxSAT-c-FPS at a 300-second time limit, with the potential to obtain better solutions surpassing the best known solution recorded in the competition evaluation.
Figures & tables
Figure 1: Overview of our framework’s architecture and solving flow. (a) GPU Differentiable Optimization . The differentiable GPU optimization maintains a logit vector per variable and evaluates hard and soft clause satisfaction in a unified forward pass. A hierarchical loss prioritizes hard clause satisfaction besides optimizing the weighted soft objective. (b) Partial Guidance Mode . Confidence-ranked variable assignments from N independently Gumbel-perturbed samples are injected as soft guidance clauses into the original WCNF, enabling parallel guided search across N CPU solver threads. (c) Phase Initialization Mode . The full GPU assignment seeds the initial internal branching phase of the CDCL-based solver. Optionally, a variant utilizes N threads to run the CPU solver using the same initialization with distinct random seeds to diversify search paths.
Solver Configuration
60 s
300 s
Score
Δ
Score
Δ
TT / SPB (single-thread)
0.866/0.876
—/—
0.925/0.926
—/—
TT / SPB -PI (single-thread)
0.883/0.900
+0.017/+0.024
0.944/0.950
+0.019/+0.024
TT / SPB -PG (multi-thread N =50)
0.903/0.910
+0.037/+0.034
0.970/0.970
+0.045/+0.044
Table 1: Average solution score across all 229 MSE 2024 anytime weighted instances at 60 s and 300 s runtime limits. Bold marks the best-performing configuration. Δ reports absolute improvement over the respective baseline. Values are reported as TT / SPB .
Figure 2: Per-instance sorted score on all 229 MSE 2024 anytime weighted instances at 60 s (left) and 300 s (right). The red dashed line marks a score of 1.0 (best-known MSE 2024 result). Both guidance modes consistently outperform their respective baselines across all instances, with partial guidance providing the largest improvement.
Figure 3: Per-instance score distribution of 50 Gumbel-perturbed guidance thread scores at 300 s for 10 selected instances. Each box spans the IQR; the white line marks the median; whiskers extend to the min/max of all 50 scores; the star ( ⋆ ) marks the best-of-50 result; the dotted line marks the single-thread original baseline. (60 s results in Appendix B .)
Figure 4: Per-instance distribution of 50 seed scores at 300 s for the same 10 instances as Figure 3 . Each box spans the IQR; the white line marks the median; whiskers extend to the min/max of all 50 scores; the star ( ⋆ ) marks the best-of-50 result; the diamond ( ⋄ ) marks the single-thread PI score; the dotted line marks the single-thread original baseline. (60 s results in Appendix B .)
Configuration
60 s
300 s
Score
Δ
Score
Δ
TT / SPB (single-thread)
0.527/0.587
—/—
0.797/0.751
—/—
TT / SPB -PI (single-thread)
0.639/0.822
+0.112/+0.235
0.917/0.984
+0.120/+0.233
TT / SPB (multi-seed, N =50)
0.633/0.595
+0.106/+0.008
1.001/0.777
+0.204/+0.026
TT / SPB -PI (multi-seed, N =50)
0.672/0.823
+0.145/+0.236
1.032/1.010
+0.235/+0.259
Table 2: Comparison of GPU-guided phase initialization against the multi-seed portfolio baseline on the 20 best-performing instances. Δ reports absolute improvement over the respective single-thread baseline. Values are reported as TT / SPB .
Stage
Description
Avg (s)
Median (s)
Max (s)
(1) Preprocessing
3MaxSAT conversion, tensor gen., GPU load
34.54
6.06
553.6
(2) Optimization
Gradient-based optimization (10 epochs)
12.76
1.70
478.5
(3) Guidance gen.
Sample N =50 assignments, save and transfer
2.45
1.75
29.3
Total
49.74
9.17
1045.8
Table 3: GPU pre-solving overhead per instance over 229 MSE 2024 instances. Timings are solver-independent; all CPU solvers share the same GPU output.
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Instance
#V
#H
#S
TT
TT -PG
TT -PI
SPB
SPB -PG
SPB -PI
DT-TicTacToe-L127-D6-AB5
278K
2527K
765
0.610
1.405
1.092
0.881
2.063
1.256
DT-Heart-CL-L127-D6-AB5
869K
7032K
236
0.537
1.175
1.288
0.573
1.446
0.734
DT-TicTacToe-L127-D6-AB3
278K
2527K
765
0.773
1.351
0.882
0.843
1.648
1.261
Syn-R2-16-S9
433K
1297K
935
0.532
1.075
0.853
0.593
0.913
1.000
SwitchAct-OR1200-66
532K
1940K
66
1.000
1.000
1.000
0.385
1.000
1.000
DT-Heart-CL-L15-D3-AB6
19K
125K
236
0.717
1.129
1.101
0.723
0.902
0.967
Appendix
Table 4: 20 selected instances based on average score improvement across all methods and runtime limits. #V, #H, #S denote the number of variables, hard clauses, and soft clauses in the original WCNF. Shown scores are recorded at 300 s.
Figure 5: Per-instance score distribution of 50 Gumbel-perturbed guidance thread scores at 60 s for 10 selected instances. Each box spans the IQR; the white line marks the median; whiskers extend to the min/max of all 50 scores; the star ( ⋆ ) marks the best-of-50 result; the dotted line marks the single-thread original baseline.
Figure 6: Per-instance distribution of 50 seed scores at 60 s for the same 10 instances as Figure 5 . Each box spans the IQR; the white line marks the median; whiskers extend to the min/max of all 50 scores; the star ( ⋆ ) marks the best-of-50 result; the diamond ( ⋄ ) marks the single-thread PI score; the dotted line marks the single-thread original baseline.
Boolean satisfiability (SAT) problem, the first problem proven to be NP-complete, has become a fundamental challenge in computational complexity, with widespread applications in optimization and verification across many domains. Despite significant algorithmic advances over the past two decades, the performance of SAT solvers has improved at a limited pace. Notably, the 2025 competition winner shows only about a 2X improvement over the 2006 winner in SAT Competition performance after nearly 20 years of effort. This paper introduces GaloisSAT, a novel hybrid GPU-CPU SAT solver that integrates a differentiable SAT solving engine powered by modern machine learning infrastructure on GPUs, followed by a traditional CDCL-based SAT solving stage on CPUs. GaloisSAT is benchmarked against the latest versions of state-of-the-art solvers, Kissat and CaDiCaL, using the SAT Competition 2024 benchmark suite. Results demonstrate substantial improvements in the official SAT Competition metric PAR-2 (penalized average runtime with a timeout of 5,000 seconds and a penalty factor of 2). Specifically, GaloisSAT achieves an 8.41X speedup in the satisfiable category and a 1.29X speedup in the unsatisfiable category compared to the strongest baselines.
Curie Kim, Carsten Portner, Mingju Liu +6
University of Maryland, College Park, MD, USA. · NVIDIA Research, Santa Clara, CA, USA. · NVIDIA Research, Austin, TX, USA. +3
This paper presents a hybrid CPU-GPU framework for solving combinatorial scheduling problems formulated as Integer Linear Programming (ILP). While scheduling underpins many optimization tasks in computing systems, solving these problems optimally at scale remains a long-standing challenge due to their NP-hard nature. We introduce a novel approach that combines differentiable optimization with classical ILP solving. Specifically, we utilize differentiable presolving to rapidly generate high-quality partial solutions, which serve as warm-starts for commercial ILP solvers (CPLEX, Gurobi) and rising open-source solver HiGHS. This method enables significantly improved early pruning compared to state-of-the-art standalone solvers. Empirical results across industry-scale benchmarks demonstrate up to a 10× performance gain over baselines, narrowing the optimality gap to <0.1%. This work represents the first demonstration of utilizing differentiable optimization to initialize exact ILP solvers for combinatorial scheduling, opening new opportunities to integrate machine learning infrastructure with classical exact optimization methods across broader domains.
Mingju Liu, Jiaqi Yin, Alvaro Velasquez +1
University of Maryland, College Park, Maryland, USA · University of Colorado, Boulder, Colorado, USA
We present Accelerated Fourier SAT (AFSAT), a GPU-accelerated solver for pseudo-Boolean satisfiability based on continuous local search (CLS). AFSAT realises the proof-of-concept approach, FastFourierSAT, into a fully-engineered solver supporting any heterogeneous mixture of symmetric constraint types and lengths within a single problem instance. Using the JAX compiler, AFSAT leverages pure function composition, automatic vectorisation, automatic differentiation, and just-in-time (JIT) compilation to perform massively parallel CLS across batches of candidate assignments. We demonstrate substantially improved numerical stability, runtime performance, and memory efficiency over the proof-of-concept. We achieve this by way of identifying and addressing various limitations that arise from memory latency and floating-point representation, as well as leveraging automatic parallelisation and compact representations. The inherent representational and stability limitations of floating point are partially addressed by a tailored discrete Fourier transform implementation. We achieve near-linear throughput when scaling to multiple accelerators via JAX array sharding.
Cody J Christopher, Charles Gretton
School of Computing, Australian National University, Canberra, Australia.