# Learning MAX-SAT from Contextual Examples for Combinatorial Optimisation

arXiv: https://arxiv.org/abs/2202.03888 · HTML: https://mlsanity.com/paper/2202.03888/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 56 references that are in the map.
- First posted on arXiv 8 Feb 2022.

## Builds on (most cited first, 5 of 5)

- [SATNet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver](https://mlsanity.com/paper/1905.12149/) (2019)
- [Counterfactual Risk Minimization: Learning from Logged Bandit Feedback](https://mlsanity.com/paper/1502.02362/) (2015)
- [Discovering Cyclic Causal Models with Latent Variables: A General SAT-Based Procedure](https://mlsanity.com/paper/1309.6836/) (2013)
- [MLIC: A MaxSAT-Based framework for learning interpretable classification rules](https://mlsanity.com/paper/1812.01843/) (2018)
- [Structured Learning Modulo Theories](https://mlsanity.com/paper/1405.1675/) (2014)

## Built on by (most cited first, 8 of 8)

- [Feasibility-Aware Decision-Focused Learning for Predicting Parameters in the Constraints](https://mlsanity.com/paper/2510.04951/) (2025)
- [torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem](https://mlsanity.com/paper/2402.03640/) (2024)
- [Application of AI to formal methods - an analysis of current trends](https://mlsanity.com/paper/2411.14870/) (2024)
- [Machine Learning for Combinatorial Optimisation of Partially-Specified Problems: Regret Minimisation as a Unifying Lens](https://mlsanity.com/paper/2205.10157/) (2022)
- [Reasoning in Neurosymbolic AI](https://mlsanity.com/paper/2505.20313/) (2025)
- [Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives](https://mlsanity.com/paper/2508.20978/) (2025)
- [Repair Before Veto: Repair-Augmented Constraint Learning for Contextual Decisions](https://mlsanity.com/paper/2606.02326/) (2026)
- [Repair Before Veto, When Repair Is Hidden: Quantum-Accessible Features for Repair-Augmented Constraint Learning](https://mlsanity.com/paper/2606.08020/) (2026)

## Abstract (arXiv)

Combinatorial optimisation problems are ubiquitous in artificial intelligence. Designing the underlying models, however, requires substantial expertise, which is a limiting factor in practice. The models typically consist of hard and soft constraints, or combine hard constraints with an objective function. We introduce a novel setting for learning combinatorial optimisation problems from contextual examples. These positive and negative examples show - in a particular context - whether the solutions are good enough or not. We develop our framework using the MAX-SAT formalism as it is simple yet powerful setting having these features. We study the learnability of MAX-SAT models. Our theoretical results show that high-quality MAX-SAT models can be learned from contextual examples in the realisable and agnostic settings, as long as the data satisfies an intuitive "representativeness" condition. We also contribute two implementations based on our theoretical results: one leverages ideas from syntax-guided synthesis while the other makes use of stochastic local search techniques. The two implementations are evaluated by recovering synthetic and benchmark models from contextual examples. The experimental results support our theoretical analysis, showing that MAX-SAT models can be learned from contextual examples. Among the two implementations, the stochastic local search learner scales much better than the syntax-guided implementation while providing comparable or better models.