Using Large Language models to solve optimization problems - A taxonomy of methods with evaluation on traveling salesman and vehicle routing problems

Abstract

This thesis explores the use of Large Language models (LLMs) to solve optimization problems. This is achieved by defining, developing and evaluating three method which utilize the LLM in different ways, namely, as algorithm implementer, optimizer and hyperparameter optimizer. Evaluation is mainly performed on the traveling salesman problem and capacitated vehicle routing problems. Performance, limitations and challenges are discussed for the three methods. Results shows that LLM is able to effectively implement simple algorithm and heuristics, but not algorithms that achieve state-of-the-art performance. LLM is also shown to be an effective optimizer for small scale optimization problems but lacks the ability to effectively perform optimization for problems of higher complexity. However, the performance is able to be improved by the use of self reflection and problem reformulations. LLM used as hyperparameter optimizer achieves the highest performance, although relies on preexisting high performance algorithms or heuristics. LLMs are also shown to outperform other simple hyperparameter optimization methods such as grid search and random search. Keywords: