Combinatorial Optimization Research Center


Tuesday, November 12, 2002, 9:30 AM

Schapiro 412


       Maria Chudnovsky
       Princeton University

       Strong Perfect Graph Theorem

   A graph is called perfect if for every induced subgraph the size of its largest clique equals the minimum number of colors needed to color its vertices. In 1960's Claude Berge made a conjecture that has become one of the most well-known open problems in graph theory: any graph that contains no induced odd cycles of length greater than three or their complements is perfect. This conjecture is know as the Strong Perfect Graph Conjecture.

   We call graphs containing no induced odd cycles of length greater than three or their complements Berge graphs. Some classic examples of perfect graphs are bipartite graphs, complements of bipartite graphs, line graphs of bipartite graphs, and their complements. It has been conjectured that any Berge graph either belongs to one of these four basic classes or can be decomposed in certain ways into smaller basic pieces.

   Recently we have been able to prove a statement similar to that, except that we need five basic classes instead of four, and consequently, the Strong Perfect Graph Theorem.

   This is joint work with Neil Robertson, Paul Seymour and Robin Thomas.

       Andy Conn

       Error estimates and poisedness in multivariate polynomial interpolation
      and derivative-free optimization

   Much of nonlinear optimization depends upon using models for the problem, for example "Trust Region Methods". Moreover, for efficient algorithms these models need to be sufficiently accurate.Typically they are Taylor series based. In derivative free optimization we need to use other models.
   We show how to derive error estimates between a function and its interpolating polynomial and between their corresponding derivatives. We will also indicate the relationship with the convergence of model based algorithms. The derivation is based on the concept of well-poisedness for the interpolation set, directly connecting the accuracy of the error estimates with the geometry of the points in the set. Prior existing error estimates make use of less intuitive geometrical conditions.
This is joint work with Katya Scheinberg and Luis Vicente.

       Gerard Cornuejols
       Carnegie Mellon University

       Recent Advances in Cutting Plane Theory

  In this talk, we survey several classical cutting planes for mixed integer programs. In particular, we discuss the relation between split cuts, Gomory mixed integer cuts and intersection cuts. These connections are then used to generate better cutting planes (joint work with Kent Andersen and Yanjun Li).

       Zonghao Gu
       ILOG Cplex

       Quadratic Programming and Mixed Integer Quadratic Programming: Algorithms and Implementation

  We see a growing interest in the financial services industry for mixed integer quadratic programming (MIQP), particularly as it applies to the solution of mean-variance portfolio optimization models. A crucial component in such techniques, as in mixed integer linear programming, is the ability to quickly reoptimize the relaxations that occur at the nodes of the search tree as a result of adding new variable bounds. While effective implementations of algorithms for the solution of quadratic programming (QP) problems have existed for some time, to our knowledge effective implementations of QP algorithms with restart capabilities, such as simplex-based algorithms, have not been available. We will discuss the new, simplex-based QP algorithms that have been implemented in CPLEX, and the key issues that arose in developing these algorithms. Their performance will be compared to the CPLEX barrier algorithm as applied to convex QPs.

       David Shmoys
       Cornell University

       Approximation algorithms for facility location and network design problems

   There has been a great deal of recent progress in research on the design and analysis of approximation algorithms for NP-hard problems, thereby expanding the breadth and depth of techniques used in this area. For relatively simple models, such as the uncapacitated facility location problem and the k-median problem, there are now several approaches that yield algorithms with strong performance guarantees. Furthermore, there are also a number of significant generalizations and variants for which comparable results can be obtained, such as extensions that incorporate notions of fault-tolerance (in facilities serving demand points) or in requiring additional connectivity properties (e.g., among the facilities). We shall survey some of the ideas (for both the algorithms' design and analysis) that have been used in obtaining these results.

       Mikkel Thorup
       AT&T Research

       Load Optimal MPLS Routing With N+M Labels

   MPLS is a relatively new routing protocol for internet routers, currently being deployed by many large ISPs, which assigns labels to packets which control their routing. One use of MPLS is traffic engineering, specifing routes to control link loads. Previous work on this specified traffic paths using at least N^2 labels in the worst case. However, an interesting feature of MPLS is that a single label can specify a tree from all sources to a given destination.
   We show that a basic solution to minimum-cost multi-commodity flow problems can be decomposed into at most N+M such trees. Thus we get optimal load-based traffic engineering with at most N+M labels.
   In addition to the theoretical results, we report on some experiments demonstrating the actual gains on some concrete networks. Also, we will discuss MPLS in some more detail, pointing to some natural optimization problems that arises.

       Robert Weismantel
       Uni. Magdeburg

       From Integral Bases to an Integer Programming Algorithm

   This talk deals with the design of a new integer programming algorithm that is based on the theory of irreducible sets of points. We will explain the latter issue in detail and demonstrate on computational results that this approach is promissing.

       Peter Winkler
       Bell Labs

       Graph Coloring and Optical Networks

   Technology keeps changing in the optical communications world, but somehow graph coloring is always in the picture. We'll give some examples of new problems requiring (1) old theorems, (2) new theorems, and (3) new conjectures. Along the way we will report on some joint work with Bell Labs colleagues Penny Haxell, Gordon Wilfong and Lisa Zhang.

       Steve Wright
       University of Wisconsin

       Solving Stochastic Optimization Problems on Computational Grids

  We discuss a bundle/trust-region algorithm for solving two-stage linear stochastic programming problems with recourse and its implementation on a computational grid. Grids are parallel computing platforms assembled from workstations, PCs, PC clusters, and conventional parallel computers. We discuss results obtained by using our code in conjunction with sampling techniques to solve many instances of sampled approximations with large sample sizes. We are able to obtain high-quality solutions to several benchmark problems in the literature, and to explore various properties of these problems, such as the size and dimensionality of the solution set and its sensitivity.
  This talk represents joint work with Jeff Linderoth (Lehigh University) and Alex Shapiro (Georgia Tech).