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

**Harvard**

Wedelin, D. (2013) *Revisiting the in-the-middle algorithm and heuristic for integer programming and the max-sum problem*.

** BibTeX **

@unpublished{

Wedelin2013,

author={Wedelin, Dag},

title={Revisiting the in-the-middle algorithm and heuristic for integer programming and the max-sum problem},

abstract={We consider a very simple algorithm to solve large scale 0-1 integer linear programs - and a simple heuristic to encourage convergence to an integer so- lution - which have been very successful in commercial applications. We find it useful to revisit its main ideas and establish its relation to several known algorithms, including the generalized iterative scaling algorithm. We discuss ways to relate this linear programming based approach to the max-sum prob- lem, and show that the algorithm has a close relation to convergent message passing algorithms for MAP-inference in graphical models such as max-sum diffusion. We further discuss non-conflicting and conflicting max-sum con- straint updates, show that the two algorithms match with these concepts, and that the heuristic has a relation to the max-sum algorithm. We finally give a brief overview of known applications, including a commercial system for airline crew scheduling.},

year={2013},

keywords={In-the-middle algorithm and heuristic, optimization, Integer linear programming, max-sum problem, probabilistic inference},

note={22},

}

** RefWorks **

RT Unpublished Material

SR Electronic

ID 190782

A1 Wedelin, Dag

T1 Revisiting the in-the-middle algorithm and heuristic for integer programming and the max-sum problem

YR 2013

AB We consider a very simple algorithm to solve large scale 0-1 integer linear programs - and a simple heuristic to encourage convergence to an integer so- lution - which have been very successful in commercial applications. We find it useful to revisit its main ideas and establish its relation to several known algorithms, including the generalized iterative scaling algorithm. We discuss ways to relate this linear programming based approach to the max-sum prob- lem, and show that the algorithm has a close relation to convergent message passing algorithms for MAP-inference in graphical models such as max-sum diffusion. We further discuss non-conflicting and conflicting max-sum con- straint updates, show that the two algorithms match with these concepts, and that the heuristic has a relation to the max-sum algorithm. We finally give a brief overview of known applications, including a commercial system for airline crew scheduling.

LA eng

LK http://www.cse.chalmers.se/~dag/in-the-middlePreprint.pdf

OL 30