Search papers, labs, and topics across Lattice.
This paper introduces an automatic pipeline that leverages a large language model (LLM) to generate problem-agnostic graphs for structure-based local improvement methods in optimization. By mapping decision variables and constraints into a uniform weighted graph, the approach facilitates effective variable selection across diverse problems in the MiniZinc format. The results show a significant performance improvement, achieving a 39.5% average problem-weighted win rate against a Gurobi baseline, with further enhancements leading to a 44.0% win rate through configuration and feature ablation.
LLM-guided graph generation can more than double optimization performance, achieving a 39.5% win rate over traditional methods.
Large neighborhood search normally selects a random subset of decision variables for iterative optimization. For efficiently solving different problems, researchers tend to design variable selection strategies by taking into account structural features from different domains. In this paper, we build an automatic pipeline that is problem-agnostic to all problems in the MiniZinc format. By prompting an LLM with our semantic guidelines, we guide the LLM to produce a graph generator that maps any instance of a problem type to a uniform weighted graph, where nodes represent decision variables and edges represent constraint relationships. These problem-agnostic graphs guide our structure-based local improvement framework (SLIM) in variable selection. Meanwhile, the weighted graph enables all problem instances to share the same generic graph representation, from which the same graph features can be extracted and used for configuration selection. We evaluated our pipeline on instances across 20 MiniZinc competition problems, finding that algorithm selection achieves a 39.5% average problem-weighted win rate against a one-shot Gurobi baseline, more than doubling the best single configuration (19.3%). Configuration and feature ablation boost the performance further to 44.0%, demonstrating that LLM-based semantic generation enables effective automated structure extraction and feature extraction for constraint optimization.
