Exact linear and integer programming

Abstract: Linear and integer programming provide powerful and flexible tools for modeling and solving a variety of decision problems. Although most optimization software used today is based on inexact floating-point arithmetic, a number of recent efforts have focused on developing efficient techniques to compute exact solutions and safe bounds.

The first component of this tutorial will be a self contained introduction to the state-of-the-art in computational linear and integer programming. We will describe general-purpose algorithms such as the simplex method, branch-and-bound and the cutting-plane method. We will also discuss how these algorithms can often be extended into highly efficient problem-specific methods. The second component of this tutorial will focus on recent progress with computing exact solutions. This will include hybrid symbolic-numeric algorithms for finding exact solutions to problem instances defined with rational data, the use of directed rounding to compute valid cutting planes, and the use of interval methods to compute valid bounds. We will highlight some of the many open questions and potential areas for further progress.

The complexity of factoring univariate polynomials over the rationals.

Abstract: This tutorial will explain the algorithm behind the currently fastest implementations for univariate factorization over the rationals. The complexity will be analyzed; it turns out that modifications were needed in order to prove a polynomial time complexity while preserving the best practical performance.

The complexity analysis leads to two results: (1) it shows that the practical performance on common inputs can be improved without harming the worst case performance, and (2) it leads to an improved complexity, not only for factoring, but for LLL reduction as well.

Convex algebraic geometry and semidefinite optimization

Abstract: This tutorial will focus on basic and recent developments in convex algebraic geometry, and the associated computational methods based on semidefinite programming for optimization problems involving polynomial equations and inequalities. There has been much recent progress in this area, combining theoretical results in real algebraic geometry with semidefinite programming to develop effective computational approaches to these problems. We will make particular emphasis on sum of squares decompositions, general duality properties, infeasibility certificates, approximation/inapproximability results, as well as survey many exciting developments that have occurred in the last few years.