FORGE: Foundational Optimization Representations from Graph Embeddings
This addresses the problem of scalability and generalization in combinatorial optimization for researchers and practitioners, though it is incremental as it builds on existing representation learning and graph embedding techniques.
The paper tackles the high computational cost and lack of generalization in learning-based combinatorial optimization by introducing Forge, a framework that pre-trains a vector-quantized graph autoencoder on diverse mixed-integer programming instances without solver data, and it improves solver performance and outperforms state-of-the-art methods in tasks like predicting integrality gaps and variable hints.
Combinatorial optimization problems are ubiquitous in science and engineering. Still, learning-based approaches to accelerate combinatorial optimization often require solving a large number of difficult instances to collect training data, incurring significant computational cost. Existing learning-based methods require training dedicated models for each problem distribution, for each downstream task, severely limiting their scalability and generalization. We introduce Forge: Foundational Optimization Representations from Graph Embeddings, a framework that pre-trains a vector-quantized graph autoencoder on a large, diverse collection of mixed-integer programming (MIP) instances in an unsupervised manner, without relying on optimization solvers or optimal solutions. Vector quantization produces discrete code assignments that serve as a vocabulary for representing optimization instances. We evaluate Forge in both unsupervised and supervised settings. In the unsupervised setting, Forge embeddings effectively cluster unseen instances across problem domains and sizes. In the supervised setting, we fine-tune Forge embeddings and show that a single pre-trained model helps predicting both the integrality gap for cut-generation and variable hints for search guidance across multiple problem and size distributions. In both tasks, we improve the performance of a commercial optimization solver and outperform state-of-the-art learning-based methods. Finally, we open-source our training code, pre-trained Forge weights, and embeddings for multiple MIP distributions to foster further research in representation learning for optimization problems.