TITLE: The Quadratic Assignment Problem and Algebraic Symmetry

SPEAKER: Renata Sotirov, Ph.D.
Tilburg University, The Netherlands

DATE / TIME: Friday, August 29, 2008 / 2:30 - 3:45 p.m.

LOCATION: Room 453 Mohler Lab, 200 W. Packer Avenue

ABSTRACT: The Quadratic Assignment Problem (QAP) is a classical combinatorial optimization problem, and is also known as a generic model for various real-life problems. The QAP is an NP-hard problem, and in practice has proven to be extremely difficult to solve to optimality. Semidefinite programming has recently turned out to be a very powerful tool for providing tight relaxations for hard combinatorial problems, notably QAP.

In this talk we consider semidefinite programming relaxation of the QAP, and show how to exploit algebraic symmetry of the data matrices when present, in order to greatly reduce the size of the relaxations. This approach has allowed us to compute the best known bounds for several instances from QAP library.

BIOGRAPHY: Renata was born in Croatia. She did her undergraduate study in mathematics at University of Zagreb, Croatia. In 2000 she started her graduate study at Klagenfurt University, Austria. In 2003, after receiving a PhD she moved to Canada. There, she was a post doctoral fellow at the Department of Computing and Software, McMaster University. In 2004, Renata became a research fellow in the Department of Mathematics and Statistics, at The University of Melbourne, Australia. Since March 2006 she has been at the Department of Econometrics and Operations Research, Tilburg University, in The Netherlands. Her current position is Assistant Professor.

Renata works in the field of Optimization, particularly in the area of semidefinite programming. Her interest is in theory and applications of optimization.