### Skapa referens, olika format (klipp och klistra)

**Harvard**

Sigurdhsson, S. (2015) *Evaluating the in-the-middle algorithm on max-sum problems*. Göteborg : Chalmers University of Technology

** BibTeX **

@misc{

Sigurdhsson2015,

author={Sigurdhsson, Simon},

title={Evaluating the in-the-middle algorithm on max-sum problems},

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.},

publisher={Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,},

place={Göteborg},

year={2015},

keywords={Combinatorial optimization, Constraint programming, Graphical models, Integer linear programming, Markov random fields, Max-SAT, Max-sum, Undirected graphical models, Wedelin heuristic, Weighted constraint satisfaction},

note={64},

}

** RefWorks **

RT Generic

SR Electronic

ID 215174

A1 Sigurdhsson, Simon

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

YR 2015

AB 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.

PB Institutionen för data- och informationsteknik (Chalmers), Chalmers tekniska högskola,

LA eng

LK http://publications.lib.chalmers.se/records/fulltext/215174/215174.pdf

OL 30