Learning for Dynamic Combinatorial Optimization without Training Data
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching
Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we …
Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems
Quantum or quantum-inspired Ising machines have recently shown promise in solving combinatorial optimization problems in a short time. Real-world applications, such as time division multiple access (TDMA) scheduling for …
Combinatorial OptimizationSchedulingSelf-Improved Learning for Scalable Neural Combinatorial Optimization
The end-to-end neural combinatorial optimization (NCO) method shows promising performance in solving complex combinatorial optimization problems without the need for expert design. However, existing methods struggle with…
Combinatorial OptimizationMiLoop: Selective Memory Propagation for Neural Combinatorial Optimization
Constructive neural combinatorial optimization (NCO) has emerged as a promising paradigm that learns to construct solutions to combinatorial optimization problems (COPs) step by step, which reduces reliance on handcrafte…
Reinforcement LearningNeural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization
Neural combinatorial optimization (NCO) is a promising learning-based approach for solving challenging combinatorial optimization problems without specialized algorithm design by experts. However, most constructive NCO m…
Combinatorial OptimizationDecoder