Using Large Language models to solve optimization problems - A taxonomy of methods with evaluation on traveling salesman and vehicle routing problems
Ladda ner
Publicerad
Författare
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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:
Beskrivning
Ämne/nyckelord
Computer, science, Computer science, engineering, thesis, large language models, LLMs, optimization, fleet optimization, transport mission planning