Graph-Aware Large Language Models for Combinatorial Optimization

Abstract

This work proposes graph-aware hybrid approach that combines classical graph algorithms and Large Language Models (LLMs) to improve interpretability of the solutions for combinatorial optimization problems. The proposed framework is capable of solving such NP-hard problems as Traveling Salesman Problem (TSP), Graph Coloring, Maximum Clique, Minimum Vertex Cover and Hamiltonian Path using the optimization backend built with the use of FastAPI framework together with the LLM explanations and D3.js visualization. The proposed framework is evaluated using the datasets of TSPLIB, DIMACS and randomly generated graphs. The experimental results showed that TSP solver was able to find the solution that is 5.4% -14.5% far from the optimal tour length after 2-opt refinement, graph coloring is optimal in 4 out of 5 benchmarks and maximum clique is optimal in all evaluated datasets. Finally, the user experiment showed that LLM explanations can improve users' comprehension of the solutions without compromising the quality of the solutions.