This work has been pursued over a number of years in the context of airline
scheduling, and the described methods are implemented in a commercial system
used by many of the
world's largest airlines. I will begin with a general description of the airline
application, with challenges and common solution techniques. I will then focus
on the
in-the-middle algorithm for solving large 0-1 integer programming problems. The
foundation of the algorithm is a linear programming based dual coordinate ascent
(message passing)
algorithm, which is combined with a heuristic mechanism for more difficult
problems. Similarities to max sum-diffusion and the max-sum algorithm are
discussed. Finally, we
describe a more recent generalization to the max-sum problem, and give some
further observations.

Prof. Dag Wedelin is with the Computer Science Dept., Chalmers University of
Technology, Goeteborg, Sweden