title:  Hard Combinatorial Problems, Doubly Nonnegative Relaxations, Facial
and Symmetry Reduction, and Alternating Direction Method of Multipliers

abstract:
Semi-definite programming, SDP, relaxations have 
proven to be extremely successful
both in theory and practice for many hard combinatorial problems.
This is particularly true for the Max-Cut problem, where
problems of dimension in the thousands have been solved to optimality.
In contrast, the quadratic assignment problem, QAP, is an NP-hard
problem where dimensions bigger than $30$ are still considered hard.
SDP and in particular, the  doubly nonnegative, DNN, relaxation have
been successful in providing strong upper and lower bounds, 
and even solving many instances to optimality. 

We look at DNN relaxations for these hard problems and illustrate
several common features using the QAP.
First, We show that the Slater constraint qualification, strict feasibility,
fails. Rather than resulting in theoretical and
numerical difficulties, we show how to use facial reduction, FR, to
regularize while reducing the dimension of the problem. 
We then consider SDPs that are invariant under the action of a symmetry group. 
This results in further symmetry reduction, SR. 

The solution method of choice for the relaxations
involve interior point approaches.
These methods do not scale well and often do not obtain high accuracy solutions.
We show how to combine FR and SR efficiently.
We then see that this fits perfectly with an
alternating directions method of multipliers, ADMM. We use this
to solve some 'humongous' instances with semidefinite constraints of the order
of 250K and nonnegative constrained variables of the order of a billion.

(Based on joint work with: Hao Hu, Renata Sotirov; and
Xinxin Li, Ting Kei Pong; and Naomi Graham,  Haesol Im, Hao Sun)