CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

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

Dag Wedelin (Institutionen för data- och informationsteknik (Chalmers))

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.

Nyckelord: In-the-middle algorithm and heuristic, optimization, Integer linear programming, max-sum problem, probabilistic inference

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2013-12-31.
CPL Pubid: 190782


Läs direkt!

Länk till annan sajt (kan kräva inloggning)