Learning-augmented smooth integer programs with PAC-learnable oracles
Organizations: National Key Laboratory for Novel Software Technology, Nanjing University · School of Artificial Intelligence, Nanjing University
Abstract
We study an end-to-end learning-augmented framework for smooth integer programs, a broad class of Boolean polynomial optimization problems including MAX-CUT and MAX-k-SAT. An oracle learned from sampled instances predicts a full Boolean assignment for each unseen instance. For fixed-degree objectives, our polynomial-time pipeline, LEAP, linearizes the objective around the predicted assignment, solves an error-budgeted linear program, and rounds the fractional solution. We establish two guarantees. First, for any prediction, the approximation loss of LEAP degrades gracefully with prediction error: it is controlled by an error footprint that quantifies how much mispredicted coordinates can perturb the objective's local coefficients. Second, we bound the pseudo-dimension of the LEAP-induced cost class, yielding a PAC-style guarantee for learning an oracle from a predictor class via empirical risk minimization on instances from an unknown distribution. Together, these results give an end-to-end bound that separates the expected footprint loss of the best oracle in the class from the statistical error of learning. In experiments on MAX-CUT and MAX-SAT, LEAP substantially repairs imperfect predictions, empirical risk minimization selects effective oracle candidates, and the pipeline scales to application benchmarks with up to two million clauses.
Figures & tables
| Symbol | Meaning |
|---|---|
| Number of Boolean variables and polynomial degree. | |
| Smooth polynomial objective and its smoothness parameter. | |
| An optimal assignment and the optimal value . | |
| Oracle prediction. | |
| Prediction error . | |
| Error budget of the footprint relaxation. |
| Family | Instances | Variables | Clauses | Width |
|---|---|---|---|---|
| Deezer | 40 | 25 / 156 | 169 / 1 684 | 2.00 / 2 |
| Decision trees | 14 | 27 015 / 82 071 | 231 206 / 660 735 | 5.27 / 98 |
| BDD optimization | 23 | 6 491 / 21 190 | 453 237 / 1 887 499 | 2.75 / 128 |
| Rule-based classifiers | 38 | 27 611 / 141 265 | 359 859 / 1 970 958 | 2.81 / 97 |
| Single-machine scheduling | 31 | 26 343 / 43 672 | 734 582 / 1 775 621 | 2.97 / 3 |
| Judgment aggregation | 38 | 12 894 / 22 994 | 296 276 / 1 567 566 | 2.89 / 3 |
Appendix figures & tables7 assets
Supplementary material from the paper’s appendix.
Appendix
| Class | Variants | Count |
|---|---|---|
| Annealing SLS | Simulated annealing ( Kirkpatrick et al., 1983 ) | 4 |
| WalkSAT-style SLS | GSAT, MaxWalkSAT, weighted and restart MaxWalkSAT ( Selman et al., 1992 ; Selman et al., 1996 ) | 16 |
| ProbSAT-style SLS | ProbSAT-like and SATLike-style search ( Balint and Schöning, 2012 ) | 8 |
| GNN predictors | GGNN, NeuroSAT, and GCN ( Li et al., 2016 ; Selsam et al., 2019 ; Kipf and Welling, 2017 ) | 9 |
| Family | Source application |
|---|---|
| Deezer | Partition social ego networks to maximize crossing edges. |
| Decision trees | Learn accurate decision trees under depth and size bounds. |
| BDD optimization | Learn bounded-depth binary decision diagram classifiers. |
| Rule-based classifiers | Learn Boolean rules balancing classification accuracy and complexity. |
| Single-machine scheduling | Maximize on-time jobs subject to release times, processing requirements, and dependencies. |
| Judgment aggregation | Find consistent collective rankings minimizing disagreement with voter or majority preferences. |
Learning-Augmented Algorithms
Learning-augmented algorithms use predictions to improve algorithmic performance while retaining guarantees when predictions are wrong.
See all 58 papers