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

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/215174
Download file(s):
File Description SizeFormat 
215174.pdfFulltext485 kBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Evaluating the in-the-middle algorithm on max-sum problems
Authors: Sigurdhsson, Simon
Abstract: 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.
Keywords: Data- och informationsvetenskap;Computer and Information Science
Issue Date: 2015
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/215174
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.