University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Colloquium - Henry WolkowiczExport this event to calendar

Friday, September 18, 2020 — 3:30 PM EDT

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)

S M T W T F S
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
  1. 2020 (92)
    1. November (1)
    2. October (1)
    3. September (12)
    4. August (11)
    5. July (17)
    6. June (11)
    7. May (6)
    8. March (11)
    9. February (11)
    10. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)