Return to Colloquia & Seminar listing
Lattice-based approaches to integer optimization - a tutorial, part II
Optimization| Speaker: | Bala Krishnamoorthy, Washington State University |
| Location: | 2112 MSB |
| Start time: | Thu, Apr 29 2010, 4:30PM |
This tutorial will introduce the fundamentals of lattices, and problems on lattices such as the shortest vector problem (SVP) and closest vector problem (CVP). We will discuss these problems from a computational complexity point of view. Basis reduction (BR) is one of the widely used methods to solve instances of SVP and CVP approximately. After motivating procedures for BR in two dimensions, we will discuss BR algorithms in general. We will also talk about the efficiencies of such algorithms in practice. BR is one of the key steps in Lenstra-type algorithms for solving integer optimization or integer programming (IP) problems in polynomial time when the dimension is fixed. But such algorithms have not been implemented so far. We will focus on BR-based approaches to IP that have sound mathematical foundations but have also proven effective in practice. We will discuss BR-based reformulations for general IP instances, and the effectiveness of standard branch-and-bound approaches for solving these instances. We will also discuss lattice-based approaches to specific class of problems such as number partitioning.
This is part II of this tutorial; part 1 is run in the student-run discrete math seminar on Thursday at noon.