Alk. Modul előadások

November 8.

Naveen Garg, Jochen Konemann. ''Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems''​

This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for min-cost flow computations in computing maximum concurrent flow and min-cost multicommodity flow; this yields much faster algorithms when the number of commodities is large.

November 15.

C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W.P. Savelsbergh, P. H. Vance. ''Branch-and-Price: Column Generation for Solving Huge Integer Programs''​

We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e. implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch-and-bound algorithms, including special branching rules and effient ways to solve the LP relaxation.

November 22.

Alexandre Belloni. ''Lecture Notes for IAP 2005 Course Introduction to Bundle Methods''​

November 29.

December 6.

December 13.