In English

Evaluating the in-the-middle algorithm on max-sum problems

Simon Sigurdhsson
Göteborg : Chalmers tekniska högskola, 2015. 64 s.
[Examensarbete på avancerad nivå]

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.

Nyckelord: Combinatorial optimization, Constraint programming, Graphical models, Integer linear programming, Markov random fields, Max-SAT, Max-sum, Undirected graphical models, Wedelin heuristic, Weighted constraint satisfaction

Publikationen registrerades 2015-04-14. Den ändrades senast 2015-04-14

CPL ID: 215174

Detta är en tjänst från Chalmers bibliotek