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

Publicerad

Författare

Typ

Examensarbete för masterexamen
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

Citation

Arkitekt (konstruktör)

Geografisk plats

Byggnad (typ)

Byggår

Modelltyp

Skala

Teknik / material

Index

item.page.endorsement

item.page.review

item.page.supplemented

item.page.referenced