Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces LM-GRASP, a novel metaheuristic framework that reformulates the construction phase of the GRASP algorithm as an online imitation learning task, allowing for instance-specific training without reliance on large offline datasets. By using a decoder-only Transformer as the constructive policy and a local search procedure as an expert oracle, LM-GRASP generates high-quality solutions dynamically, eliminating the need for problem-specific feature engineering. Evaluated on the challenging Taillard PFSP benchmark, LM-GRASP demonstrates a significant performance improvement over traditional GPU-GRASP, outperforming it by an average of 28.4 makespan units, highlighting the effectiveness of instance-specific learning in combinatorial optimization.
Instance-specific language models can outperform traditional combinatorial optimization methods, achieving significant gains without extensive pretraining.
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.