Title:
Hard
Combinatorial
Problems,
Doubly
Nonnegative
Relaxations,
Facial
and
Symmetry
Reduction,
and
Alternating
Direction
Method
of
Multipliers
| Speaker: | Henry Wolkowicz |
| Affiliation: | University of Waterloo |
| Zoom: | Please email Emma Watson |
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)