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

• URL: http://arxiv.org/abs/2606.18514v1
• Date: Tue, 16 Jun 2026 22:05:51 GMT
• Title: N(CO)$^2$: Neural Combinatorial Optimization with Chance Constraints to Solve Stochastic Orienteering
• Abstract summary: We present N(CO)$2$: Neural Combinatorial Optimization with Chance cOnstraints to solve the Orienteering Problem (SOP) without the use of hand-crafteds.<n>The proposed approach reduces human effort while enabling adaptive and efficient decision-making in uncertain environments.
• Score: 7.0274229967026045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Geometric Algorithms for Neural Combinatorial Optimization with Constraints [46.17172939797694]
  Self-Supervised Learning for Combinatorial Optimization (CO) is an emerging paradigm for solving problems using neural networks.<n>We design an end-to-end differentiable framework that enables us to solve discrete constrained optimization problems with neural networks.
  arXiv  Detail & Related papers  (2025-10-28T03:49:01Z)
• Preference Optimization for Combinatorial Optimization Problems [54.87466279363487]
  Reinforcement Learning (RL) has emerged as a powerful tool for neural optimization, enabling models learns that solve complex problems without requiring expert knowledge.<n>Despite significant progress, existing RL approaches face challenges such as diminishing reward signals and inefficient exploration in vast action spaces.<n>We propose Preference Optimization, a novel method that transforms quantitative reward signals into qualitative preference signals via statistical comparison modeling.
  arXiv  Detail & Related papers  (2025-05-13T16:47:00Z)
• BOPO: Neural Combinatorial Optimization via Best-anchored and Objective-guided Preference Optimization [17.694852175354555]
  We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values.<n>Experiments on Job-shop Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods.
  arXiv  Detail & Related papers  (2025-03-10T17:45:30Z)
• Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimization [15.102119312523696]
  Combinatorial optimization (CO) problems arise across a broad spectrum of domains, including medicine, logistics, and manufacturing.<n>We propose a learning-based approach that enhances existing non-learned approximation algorithms for CO.<n>Our method is trained end-to-end in a self-supervised fashion, using a novel gradient estimation scheme that treats the approximation algorithm as a black box.
  arXiv  Detail & Related papers  (2025-02-26T18:23:07Z)
• Neural Combinatorial Optimization for Stochastic Flexible Job Shop Scheduling Problems [5.10888539576355]
  We propose a novel attention-based scenario processing module (SPM) to extend NCO methods for solving scenarios.<n>Our approach explicitly incorporates approximation information by an attention mechanism that captures the embedding of sampled scenarios.<n>Results demonstrate that our approach outperforms existing learning and non-learning methods for the flexible problem.
  arXiv  Detail & Related papers  (2024-12-18T17:05:33Z)
• Learning Joint Models of Prediction and Optimization [56.04498536842065]
  Predict-Then-Then framework uses machine learning models to predict unknown parameters of an optimization problem from features before solving. This paper proposes an alternative method, in which optimal solutions are learned directly from the observable features by joint predictive models.
  arXiv  Detail & Related papers  (2024-09-07T19:52:14Z)
• Self-Improved Learning for Scalable Neural Combinatorial Optimization [15.842155380912002]
  This work proposes a novel Self-Improved Learning (SIL) method for better scalability of neural optimization. We develop an efficient self-improved mechanism that enables direct model training on large-scale problem instances without any labeled data. In addition, we design a linear attention complexity mechanism for the computation model to efficiently handle large-scale problem instances with low overhead.
  arXiv  Detail & Related papers  (2024-03-28T16:46:53Z)
• Federated Conditional Stochastic Optimization [110.513884892319]
  Conditional optimization has found in a wide range of machine learning tasks, such as in-variant learning tasks, AUPRC, andAML. This paper proposes algorithms for distributed federated learning.
  arXiv  Detail & Related papers  (2023-10-04T01:47:37Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.