# N(CO)2: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 29 references that are in the map.
- First posted on arXiv 16 Jun 2026.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Global Self-Attention as a Replacement for Graph Convolution](https://mlsanity.com/paper/2108.03348/) (2021)
- [Learning the Travelling Salesperson Problem Requires Rethinking Generalization](https://mlsanity.com/paper/2006.07054/) (2020)
- [Winner Takes It All: Training Performant RL Populations for Combinatorial Optimization](https://mlsanity.com/paper/2210.03475/) (2022)
- [Unsupervised Learning for Solving the Travelling Salesman Problem](https://mlsanity.com/paper/2303.10538/) (2023)
- [LinSATNet: The Positive Linear Satisfiability Neural Networks](https://mlsanity.com/paper/2407.13917/) (2024)
- [USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems](https://mlsanity.com/paper/2107.07508/) (2021)
- [Learning to Optimize with Stochastic Dominance Constraints](https://mlsanity.com/paper/2211.07767/) (2022)
- [Solving Stochastic Orienteering Problems with Chance Constraints Using Monte Carlo Tree Search](https://mlsanity.com/paper/2409.03170/) (2024)
- [Boosting Graph Search with Attention Network for Solving the General Orienteering Problem](https://mlsanity.com/paper/2109.04730/) (2021)
- [Solving Stochastic Orienteering Problems with Chance Constraints Using a GNN Powered Monte Carlo Tree Search](https://mlsanity.com/paper/2409.04653/) (2024)
- [Leveraging LLMs for Mission Planning in Precision Agriculture](https://mlsanity.com/paper/2506.10093/) (2025)
- [Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems](https://mlsanity.com/paper/2412.14052/) (2024)

## Abstract (arXiv)

Neural combinatorial optimization (NCO) offers a promising alternative to traditional heuristic-based methods for solving complex graph optimization problems by proposing to learn heuristics through data. This class of problems frequently arises in automation, as it can be used to model a variety of applications. While NCO has been extensively studied for deterministic combinatorial optimization problems, there are only a few works that aim to solve stochastic combinatorial optimization problems. In this work, we present N(CO)2: Neural Combinatorial Optimization with Chance cOnstraints to solve the Stochastic Orienteering Problem (SOP) without the use of hand-crafted heuristics. By integrating a reinforcement learning (RL) framework, the model optimizes path selection under uncertainty, effectively balancing exploration and exploitation. Empirical results demonstrate that our method generalizes well across diverse SOP instances, achieving competitive performance compared to the state-of-the-art mixed-integer linear program (MILP) for the task. The proposed approach reduces human effort in heuristic design while enabling adaptive and efficient decision-making in uncertain environments.