SDP Bounds and a Peaceman-Rachford Splitting Method for the Quadratic Minimum Spanning Tree Problem

Abstract: In the quadratic minimum spanning tree problem (QMSTP), one wants to find the minimizer of a quadratic function over all possible spanning trees of a graph. In this talk we show how to formulate the QMSTP as mixed-integer semidefinite programs exploiting the algebraic connectivity of a graph. Based on these formulations, we derive a doubly nonnegative relaxation (DNN) for the QMSTP and present valid inequalities to strengthen the relaxation using the Chvátal-Gomory procedure for mixed-integer conic programming. We present a version of the Peaceman-Rachford splitting method, which allows us to solve the DNN relaxation and thereby obtain strong bounds on the QMSTP.
This is joint work with Frank de Meijer, Renata Sotirov and Melanie Siebenhofer.