Combinatorial Optimization via LLM-driven Iterated Fine-tuning
This work addresses combinatorial optimization problems where constraints are nuanced and locally specified, offering a hybrid AI-driven approach that is incremental in nature.
The paper tackles the challenge of integrating flexible, context-dependent constraints into combinatorial optimization by combining Large Language Models (LLMs) with traditional algorithms, resulting in a framework that more effectively balances local constraint flexibility with global optimization compared to baseline methods.
We present a novel way to integrate flexible, context-dependent constraints into combinatorial optimization by leveraging Large Language Models (LLMs) alongside traditional algorithms. Although LLMs excel at interpreting nuanced, locally specified requirements, they struggle with enforcing global combinatorial feasibility. To bridge this gap, we propose an iterated fine-tuning framework where algorithmic feedback progressively refines the LLM's output distribution. Interpreting this as simulated annealing, we introduce a formal model based on a "coarse learnability" assumption, providing sample complexity bounds for convergence. Empirical evaluations on scheduling, graph connectivity, and clustering tasks demonstrate that our framework balances the flexibility of locally expressed constraints with rigorous global optimization more effectively compared to baseline sampling methods. Our results highlight a promising direction for hybrid AI-driven combinatorial reasoning.