| [home] - [up] |
Abstract: The main method for solving integer optimization problems is linear programming based branch-and-bound, typically enhanced by strong cutting planes. A huge progress in computational integer optimization, and in particular combinatorial optimization, has been booked during the past couple of decades by refined implementations of such branch-and-bound methods. There are, however, certain classes of instances for which branch-and-bound does not work in practice. In some cases it is quite easy to see that the linear relaxation simply does not provide interesting information, and in other cases it is hard to explain why it does not work. This, along, with interesting mathematical questions, have motivated the search for alternative methods. In this lecture I will review some alternatives to branch-and-bound, and mainly concentrate on lattice based methods, primal augmentation methods and test sets. I will also briefly mention Barvinok's algorithm for counting integer points in a rational polytope. The last part of the lecture will consist of a presentation of a lattice based method for solving integer feasibility problems.
Colloquium - 16:00
Abstract: Many 'real-world' problems, especially in traffic applications, can be modeled as static network routing or flow problems. Often however, a static model does not give a sufficiently exact picture of the considered application and one has to take care of the time-dependencies as well. A nice and powerful framework that captures such time-dependencies is the theory of dynamic network flows. In this theory the time-expanded network is a well-known tool since it allows to map dynamic, i.e., time-dependent problems to static ones. But it has an important disadvantage: the time-expanded network is extremely large and thus seems to be irrelevant for any practical applications.
In this talk we report on a project for routing automated guided vehicles in the Hamburg Harbor. We show various problems that occur when using a static model for this application and therefor present a dynamic model for it. Building up on the time-expanded network, we give an implicit time expansion, that still captures the existing time-dependencies. This dynamic approach not only allows a very compact model but can also be used for designing practically efficient algorithms.