LM-GRASP: Instance-Specific Language Models for Combinatorial Construction via Online Imitation Learning
LM-GRASP employs online imitation learning with Transformer to generate instance-specific solutions, outperforming traditional heuristics with 28.4 units improvement on PFSP.
Key Findings
Methodology
This paper introduces a novel framework that transforms the randomized constructive phase of GRASP into a sequence generation task, trained via behavioral cloning. Using a decoder-only Transformer, the policy conditions on the entire construction history, enabling non-myopic decision-making. The local search acts as an expert oracle, producing high-quality solution trajectories that are used to iteratively train the model online, without external datasets or offline pretraining. The approach leverages the objective function interface solely, making it highly adaptable. Experiments on Taillard PFSP instances show an average improvement of 28.4 makespan units over GPU-GRASP, validating the effectiveness of instance-specific, online-trained language models.
Key Results
- On the Taillard benchmark (ta51-ta60), LM-GRASP achieves an average makespan reduction of 28.4 units, surpassing GPU-GRASP by a significant margin, especially on instances with many unknown optima.
- The method requires no offline data or pretraining, relying solely on dynamically generated high-quality trajectories, demonstrating strong adaptability and solution quality.
- Hardware acceleration (GPU) provides a comparable performance boost (27.2 units), indicating that learned policies can match hardware improvements in practical scenarios.
Significance
This work addresses the core limitations of static heuristics in combinatorial optimization by introducing a fully data-driven, instance-specific approach. It leverages deep autoregressive models to capture global structural dependencies, enabling solutions that adapt dynamically to each problem instance. The elimination of pretraining costs and feature engineering lowers barriers for practical deployment, opening pathways for intelligent, self-improving optimization systems in industrial scheduling, logistics, and beyond. The approach also demonstrates that deep sequence models can effectively learn complex solution structures directly from problem-specific trajectories, marking a significant step toward autonomous optimization.
Technical Contribution
The main technical innovation lies in formulating the constructive phase of metaheuristics as a sequence generation problem, trained via behavioral cloning on high-quality local search trajectories. The use of a decoder-only Transformer allows the model to condition on entire solution histories, capturing long-range dependencies that static heuristics cannot. The framework operates entirely online, updating the policy iteratively without external datasets or offline training, which is novel in the field. This approach bridges the gap between deep sequence modeling and combinatorial optimization, offering a flexible, instance-specific solution constructor with theoretical and practical advantages.
Novelty
This is the first work to apply a Transformer-based autoregressive model trained entirely online and from scratch for instance-specific combinatorial optimization. Unlike previous methods relying on offline pretraining or static heuristics, LM-GRASP dynamically learns the construction policy during the search process, tailored to each instance. Its unique integration of local search as an expert oracle and sequential token generation for solution construction represents a new paradigm, significantly reducing reliance on handcrafted heuristics and external data, and enabling adaptive, high-quality solutions in complex landscapes.
Limitations
- Training time can be substantial for very large or highly complex instances, as the model relies on sufficient high-quality trajectories for effective learning.
- The approach depends heavily on the local search quality; if the local search gets trapped in local optima, the learned policy may be less effective.
- Currently validated only on PFSP; applicability to other combinatorial problems remains to be demonstrated, requiring further adaptation and testing.
Future Work
Future directions include developing multi-instance training strategies to improve generalization, integrating reinforcement learning to enhance trajectory quality, and extending the framework to other problem domains such as vehicle routing, packing, or network design. Additionally, efforts to improve training efficiency, interpretability, and robustness will facilitate real-world industrial applications. Exploring hybrid models combining offline pretraining with online adaptation could further enhance performance and scalability.
AI Executive Summary
Traditional combinatorial optimization methods often rely on static, handcrafted heuristics, which, while effective in certain scenarios, struggle to adapt to complex, high-dimensional instances. These heuristics are typically myopic, focusing on local costs without capturing the broader structural dependencies within solutions. Recent advances in deep learning, especially Transformer models, have demonstrated remarkable success in sequence generation tasks, inspiring their application to optimization problems. However, most existing approaches depend on extensive offline pretraining or large datasets, limiting flexibility and adaptability.
This paper introduces LM-GRASP, a novel framework that transforms the constructive phase of the classical GRASP algorithm into a sequence generation problem. By leveraging a decoder-only Transformer conditioned on the entire solution history, LM-GRASP learns to produce high-quality solutions online, tailored to each specific instance. The training process employs behavioral cloning, where the local search acts as an expert oracle, generating trajectories that guide the model's learning. This approach eliminates the need for external data or pretraining, making it highly adaptable.
Experimental results on the Taillard PFSP benchmark demonstrate the method's effectiveness, achieving an average improvement of 28.4 units in makespan over GPU-GRASP, a significant margin in such a challenging setting. The performance is comparable to hardware acceleration gains, highlighting the potential of instance-specific, online-trained language models in practical optimization tasks. The framework’s ability to capture complex, global solution structures through sequence modeling marks a breakthrough in combining deep learning with combinatorial optimization.
Overall, LM-GRASP offers a flexible, scalable, and efficient alternative to traditional heuristics, with broad implications for industrial scheduling, logistics, and resource management. Its capacity for real-time adaptation and high solution quality paves the way for future research into autonomous, intelligent optimization systems that learn directly from problem instances without relying on costly offline datasets. Future work will explore multi-instance training, broader problem applicability, and integration with reinforcement learning to further enhance its robustness and generalization.
Deep Dive
Abstract
Machine learning for combinatorial optimization typically relies on neural constructors trained via reinforcement learning on large offline datasets for a fixed problem class-incurring high pretraining costs and generalizing poorly outside the training distribution. We propose an alternative: a metaheuristic framework that reformulates the randomized constructive phase of GRASP as an online imitation learning task, trained from scratch on each problem instance. A local search procedure acts as an expert oracle, while a decoder-only Transformer serves as the constructive policy. Unlike classical GRASP, which relies on static, myopic heuristic rules based on localized scalar costs, our approach is fully data-driven: the construction policy emerges from high-quality solutions discovered during the search itself, with no problem-specific feature engineering required. We instantiate this as LM-GRASP, a hybrid metaheuristic following an iterative learn-infer-improve cycle, training the policy online via behavioral cloning on a dynamic archive of elite trajectories-no external data or offline pretraining needed. The pipeline interfaces with the domain solely through the objective evaluator used by local search. Evaluated on the Taillard PFSP benchmark (ta51-ta60), the most discriminating block due to half its optima being unknown, LM-GRASP outperforms GPU-GRASP by 28.4 makespan units on average-comparable to the gain from GPU acceleration over sequential execution (27.2 units), though with overlapping standard deviations. This suggests instance-specific, online-trained language models are a promising, practical alternative to hand-engineered constructors, especially for landscapes resistant to classical greedy construction.