UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization

• URL: http://arxiv.org/abs/2603.11456v1
• Date: Thu, 12 Mar 2026 02:32:19 GMT
• Title: UniHetCO: A Unified Heterogeneous Representation for Multi-Problem Learning in Unsupervised Neural Combinatorial Optimization
• Abstract summary: Unsupervised neural optimization (NCO) offers an appealing alternative to supervised approaches.<n>Existing unsupervised methods are typically specialized to a single problem class.<n>UniHetCO encodes problem structure, objective terms, and linear constraints in a single input.<n>Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance.
• Score: 4.194554268792374
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Unsupervised neural combinatorial optimization (NCO) offers an appealing alternative to supervised approaches by training learning-based solvers without ground-truth solutions, directly minimizing instance objectives and constraint violations. Yet for graph node subset-selection problems (e.g., Maximum Clique and Maximum Independent Set), existing unsupervised methods are typically specialized to a single problem class and rely on problem-specific surrogate losses, which hinders learning across classes within a unified framework. In this work, we propose UniHetCO, a unified heterogeneous graph representation for constrained quadratic programming-based combinatorial optimization that encodes problem structure, objective terms, and linear constraints in a single input. This formulation enables training a single model across multiple problem classes with a unified label-free objective. To improve stability under multi-problem learning, we employ a gradient-norm-based dynamic weighting scheme that alleviates gradient imbalance among classes. Experiments on multiple datasets and four constrained problem classes demonstrate competitive performance with state-of-the-art unsupervised NCO baselines, strong cross-problem adaptation potential, and effective warm starts for a commercial classical solver under tight time limits.

Related papers

• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
  This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems.<n>The proposed method relies on a graph-based generative diffusion model that learns the discrete component of mixed-integer optimization problems.<n>The framework named Constrained Graph Diffusion (CGD) is problem-agnostic and can accommodate a broad class of mixed-integer optimization problems.
  arXiv  Detail & Related papers  (2026-08-13T10:46:18Z)
• Neural Predictor-Corrector: Solving Homotopy Problems with Reinforcement Learning [38.623998031868595]
  Homotopy paradigm appears across diverse domains such as robust optimization, global optimization, root-finding, and sampling.<n>We propose Neural Predictor-Corrector (NPC), which replaces hand-crafted NPC with automatically learned policies.<n>NPC consistently outperforms classical and specialized baselines in efficiency while demonstrating superior stability across tasks.
  arXiv  Detail & Related papers  (2026-02-03T04:19:48Z)
• Online Inference of Constrained Optimization: Primal-Dual Optimality and Sequential Quadratic Programming [55.848340925419286]
  We study online statistical inference for the solutions of quadratic optimization problems with equality and inequality constraints.<n>We develop a sequential programming (SSQP) method to solve these problems, where the step direction is computed by sequentially performing an approximation of the objective and a linear approximation of the constraints.<n>We show that our method global almost moving-average convergence and exhibits local normality with an optimal primal-dual limiting matrix in the sense of Hjek and Le Cam.
  arXiv  Detail & Related papers  (2025-11-27T06:16:17Z)
• 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)
• Heterogeneous Self-Supervised Acoustic Pre-Training with Local Constraints [64.15709757611369]
  We propose a new self-supervised pre-training approach to dealing with heterogeneous data.<n>The proposed approach can significantly improve the adaptivity of the self-supervised pre-trained model for the downstream supervised fine-tuning tasks.
  arXiv  Detail & Related papers  (2025-08-27T15:48:50Z)
• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [53.03951222945921]
  We analyze smoothed (perturbed) policies, adding controlled random perturbations to the direction used by the linear oracle.<n>Our main contribution is a generalization bound that decomposes the excess risk into perturbation bias, statistical estimation error, and optimization error.<n>We illustrate the scope of the results on applications such as vehicle scheduling, highlighting how smoothing enables both tractable training and controlled generalization.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Differentiable Quadratic Optimization For The Maximum Independent Set Problem [23.643727259409744]
  We show that pCQO-MIS scales only with the number nodes in graph, not number edges.<n>Our experimental results demonstrate the effectiveness of the proposed method compared to exact, sampling and data-centric approaches.
  arXiv  Detail & Related papers  (2024-06-27T21:12:48Z)
• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• 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)
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning [35.50454156611722]
  Reinforcement learning (RL) has recently emerged as a new framework to tackle these problems. We propose a general RL framework that not only exhibits state-of-the-art empirical performance but also generalizes to a variety class of COPs.
  arXiv  Detail & Related papers  (2021-02-14T18:05:42Z)

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.