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 OptimizationNeural 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 OptimizationDecoderDeep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
This paper introduces a new deep learning approach to approximately solve the Covering Salesman Problem (CSP). In this approach, given the city locations of a CSP as input, a deep neural network model is designed to dire…
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement Learning+1