Abstract

We introduce DyCO-GNN, a novel unsupervised learning framework for DynamicCombinatorial Optimization that requires no training data beyond the probleminstance itself. DyCO-GNN leverages structural similarities acrosstime-evolving graph snapshots to accelerate optimization while maintainingsolution quality. We evaluate DyCO-GNN on dynamic maximum cut, maximumindependent set, and the traveling salesman problem across diverse datasets ofvarying sizes, demonstrating its superior performance under tight and moderatetime budgets. DyCO-GNN consistently outperforms the baseline methods, achievinghigh-quality solutions up to 3-60x faster, highlighting its practicaleffectiveness in rapidly evolving resource-constrained settings.

 

Quick Read (beta)