Evaluating the in-the-middle algorithm on max-sum problems
Ladda ner
Typ
Examensarbete för masterexamen
Master Thesis
Master Thesis
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2015
Författare
Sigurdhsson, Simon
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
The fields of graphical modelling and constraint satisfaction have been very active in recent years, which is unsurprising given the large range of problems which may be described using such techniques. While many novel algorithms have been presented, there are still areas of the field in which improvements are possible. Reviews have uncovered strong links between the linear programming and graphical modelling fields, and it is therefore of interest to survey the possible application of linear programming methods to graphical models and constraint satisfaction problems. The in-the-middle algorithm, an approximate solution method in linear programming which has seen extensive use in the industry, was extended to max-sum problems by Grohe and Wedelin (2008). Graphical models and constraint satisfaction problems are easily translated into max-sum formulations, and the in-the-middle algorithm is therefore an ideal candidate in reformulating linear programming algorithms to the field of constraint satisfaction. This thesis presents an implementation of the in-the-middle algorithm applied to max-sum problems, which may be applied to general constraint satisfaction instances. The implementation is benchmarked against three existing high-performance exact solvers in the field, using a problem set consisting of several hundred problems. Results indicate that the in-the-middle algorithm may have potential in the fields of constraint satisfaction and graphical model optimization, but that further research is required to make the algorithm competitive. Several avenues for further research on the algorithm are proposed.
Beskrivning
Ämne/nyckelord
Data- och informationsvetenskap , Computer and Information Science