# Finding Probably Approximate Optimal Solutions by Training to Estimate the Optimal Values of Subproblems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 5 references that are in the map.
- First posted on arXiv 3 Nov 2025.

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

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [The Transformer Network for the Traveling Salesman Problem](https://mlsanity.com/paper/2103.03012/) (2021)

## Abstract (arXiv)

The paper is about developing a solver for maximizing a real-valued function of binary variables. The solver relies on an algorithm that estimates the optimal objective-function value of instances from the underlying distribution of objectives and their respective sub-instances. The training of the estimator is based on an inequality that facilitates the use of the expected total deviation from optimality conditions as a loss function rather than the objective-function itself. Thus, it does not calculate values of policies, nor does it rely on solved instances.