joint work with Renata Sotirov, Henry Wolkowicz
For specially structured SDP instances, symmetry reduction is an application of representation theory to reduce the dimension of the feasible set. For an SDP instance that fails Slater’s condition, facial reduction technique can be employed to find the smallest face of the PSD cone containing the feasible region. The resulting SDP instance is of smaller dimension and satisfies Slater’s condition. In this talk, we show that symmetry reduction and facial reduction can be exploited at the same time. Our method is simple to implement, and is applicable for a wide variety of applications of SDPs.
joint work with Franz Rendl, Renata Sotirov
The bandwidth problem asks for a simultaneous permutation of the rows and columns of the adjacency matrix of a graph such that all nonzero entries are as close as possible to the diagonal. We present novel approaches to obtain lower bounds on the bandwidth problem and introduce a vertex partition problem to bound the bandwidth of a graph. By varying sizes of partitions, we have a trade-off between quality of bounds and efficiency of computing them. To compute lower bounds, we derive several SDP relaxations. Finally, we evaluate our approach on a carefully selected set of benchmark instances.
joint work with Etienne de Klerk
The Jordan reduction, a symmetry reduction method for semidefinite programming, was recently introduced for symmetric cones by Parrilo and Permenter. We extend this method to the doubly nonnegative cone and investigate its application to a strong relaxation of the quadratic assignment problem. This reduction is then used to efficiently calculate better bounds for certain discrete energy minimization problems, which initially have the form of semidefinite programs too large to be solved directly.