Tutte Colloquium - Henry Wolkowicz

Title: Solving DNN Relaxations of the Quadratic Assignment Problem with ADMM and Facial Reduction

Abstract:

The quadratic assignment problem, QAP, has many important applications ranging from the planning of building locations of a university, to the positioning of modules on a computer chip (VLSI design), to the design of keyboards. This discrete optimization problem is arguably one of the hardest of the NP-hard problems, as problems with dimension 30 are still considered hard to solve to optimality.

The QAP in the trace formulation is modelled as the minimization of a quadratic function over the permutation matrices. The set of permutation matrices can be represented by quadratic constraints. Relaxations of these constraints are used in branch and bound solution methods. These relaxations include the eigenvalue and projected eigenvalue relaxations, as well as various semidefinite programming, SDP,  and doubly nonnegative, DNN, relaxations. These latter relaxations are particularly strong and often solve the QAP to optimality. However, they can be extremely expensive to solve.

We show that the combination of an alternating directions method of multipliers, ADMM, in combination with facial reduction, FR, works extremely well in solving the very difficult DNN relaxation.

Joint work with Danilo Elias Oliveira and YangYang Xu.