Learning for Dynamic Combinatorial Optimization without Training Data
This addresses the problem of efficient optimization in rapidly evolving, resource-constrained settings for domains like logistics and scheduling, though it is incremental as it builds on existing graph neural network methods.
The paper tackles dynamic combinatorial optimization without training data by introducing DyCO-GNN, an unsupervised framework that leverages structural similarities across time-evolving graphs, achieving high-quality solutions up to 3-60x faster than baselines.
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.