Learning for Dynamic Combinatorial Optimization without Training Data

2025/05/26 by Yiqiao Liao, Farinaz Koushanfar, Liao, Yiqiao +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Machine Learning (cs.LG) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2505.19497

openalex publication_date 2025/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We introduce DyCO-GNN, a novel unsupervised learning framework for Dynamic Combinatorial Optimization that requires no training data beyond the problem instance itself. DyCO-GNN leverages structural similarities across time-evolving graph snapshots to accelerate optimization while maintaining solution quality. We evaluate DyCO-GNN on dynamic maximum cut, maximum independent set, and the traveling salesman problem across diverse datasets of varying sizes, demonstrating its superior performance under tight and moderate time budgets. DyCO-GNN consistently outperforms the baseline methods, achieving high-quality solutions up to 3-60x faster, highlighting its practical effectiveness in rapidly evolving resource-constrained settings.

Citations

• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization
• Fast, Scalable, Warm-Start Semidefinite Programming with Spectral Bundling and Sketching
• Variational Annealing on Graphs for Combinatorial Optimization
• Distributed Constrained Combinatorial Optimization leveraging Hypergraph Neural Networks
• Controlling Continuous Relaxation for Combinatorial Optimization
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization
• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning
• DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems
• One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction
• Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
• Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Graph Neural Networks for Maximum Constraint Satisfaction
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Fast Graph Representation Learning with PyTorch Geometric
• Fully Dynamic Maximal Independent Set with Sublinear Update Time
• Graph Attention Networks
• Inductive Representation Learning on Large Graphs
• Learning Combinatorial Optimization Algorithms over Graphs
• Neural Combinatorial Optimization with Reinforcement Learning
• Efficient Combinatorial Optimization Using Quantum Annealing
• Semi-Supervised Classification with Graph Convolutional Networks
• Pointer Networks
• Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Related

• Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning
• Zero Training Overhead Portfolios for Learning to Solve Combinatorial Problems
• Moco: A Learnable Meta Optimizer for Combinatorial Optimization
• Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation
• UniCO: Towards a Unified Model for Combinatorial Optimization Problems