title:
Lagrangian and Semidefinite Programming
     Relaxations for Discrete Optimization Problems


    Henry Wolkowicz
    Dept. Comb. and Opt.
    University of Waterloo

Abstract:
Many hard combinatorial problems can be modelled 
as the minimization (or maximization) of a quadratic function subject to
quadratic constraints, denoted QQP.
These models are nonconvex in general; so
finding a global solution is itself a very hard problem.
Surprisingly, there are several important classes that are tractable.

For the nontractable cases,
we look at Lagrangian relaxations for these QQPs. These Lagrangian
relaxations are equivalent to semidefinite programming
relaxations, i.e. to the
minimization of a linear function of symmetric matrices subject to
linear and semidefinite constraints, denoted SDP. These relaxations are
convex problems that can be solved efficiently using interior-point
methods. Moreover, the bounds they provide are surprisingly tight.
We examine several instances: 
the max-cut; quadratic assignment; and graph partitioning problems.