Theme:

Linear Programming is the basis for the by now classical approach to deal with hard combinatorial optimization problems. This approach has turned out powerful for problems like the Traveling Salesman Problem, but for other types of problems, such as Graph Partition or Quadratic Assignment problems (QAP)), the linear relaxations either seem too weak or too expensive.

On the other hand, the success of interior point methods that deal with constrained nonlinear problems has led to increased interest in algorithmic nonlinear optimization in the last 15 years. In the last few years, cone LP and in particular Semidefinite programming (SDP) have turned out to be powerful tools in various branches of applied mathematics, notably for combinatorial optimization (Goemans-Williamson approximation for Max-Cut) and in System and Control theory. SDP has become a bridge between combinatorial optimization and nonlinear programming.

The breathtaking progress in algorithmic nonlinear optimization, but also in computer hardware has thrown new light on the analysis of NP-hard problems. Recently, a major break-through was achieved to solve QAP of sizes (n=30) unthinkable by conventional methods. This progress was due in part to a new nonlinear relaxation for QAP, but also to new computing facilities, allowing for massive parallel computation. Similar progress is also made in other areas, such as clique and coloring on massive graphs.

The aim of the workshop is therefore to bring together researchers from several communities, such as:

algorithmic nonlinear optimization
combinatorial optimization, dealing with computational methods for NP-hard problems
computer scientists interested in scientific parallel computing,

who share a common interest to do computations on (large-scale) hard combinatorial optimization problems.

The workshop will follow in spirit previous workshops such as:

the workshop on Quadratic Assignment and Related Problems, May 1993; at DIMACS, Rutgers University.
the Workshop on Semidefinite Programming and Interior-Point Approaches for Combinatorial Optimization Problems, May 1996; at the Fields Institute.

Back to Workshop home page