Title: Bundle methods in combinatorial optimization

Speaker: Franz Rendl, Univ. Klagenfurt
(joint work with I. Fischer, G. Gruber and R. Sotirov)

Abstract:                            

Several hard combinatorial optimization problems, such as                 
Max-Cut or Quadratic Assignment can be approximated nicely by             
Semidefinite Programs (SDP). These relaxations can be further improved    
by including combinatorial cutting planes, resulting in huge              
SDPs.                                                                     
                                                                          
We use the bundle method from nonsmooth optimization                      
to tackle these SDPs. The idea consists in identifying a basic            
model, and taking the Lagrange dual of the remaining constraints.         
                                                                          
We discuss some practical issues like finding good primal solutions,      
and identifying important cutting planes.                                 
                                                                          
Finally, we present computational                                         
results of this approach applied to the max-cut relaxation                
given by the basic SDP model intersected with the metric polytope,        
and SDP relaxations of the Quadratic Assignment Problem.                  


--------------------------------------------------------------------
Franz Rendl,   Institut fuer Mathematik,    Universitaet Klagenfurt,
A - 9020 Klagenfurt,   Austria     e-mail: franz.rendl@uni-klu.ac.at
phone: ++43 463 2700/3114 (3103 secretary)   fax: ++43 463 2700/3199 
--------------------------------------------------------------------