Title: Chordal Completions – Semidefinite Programming and Minimum Completions
Speaker: Dr Arvind Raghunathan
Affiliation: Mitsubishi Electric Research Laboratories (MERL)
Location: 217 Huxley Building
Time: 14:00 – 15:00

Abstract. A graph is chordal if every cycle of length at least four contains a chord, that is, an edge connecting two nonconsecutive vertices of the cycle. Chordal completion of a given undirected graph G is a chordal graph, on the same vertex set, that has G as a subgraph. Several classical applications in sparse linear systems, database management, computer vision, and SemiDefinite Programming (SDP) utilize chordal completions. The computation workload that results can be related to the number of edges that are added. Hence, finding the minimum number of edges that makes a graph chordal is important. We refer to this as the Minimum Chordal Completion Problem (MCCP). In this talk, we will present results on an application of completions in SDPs and the solution of MCCP.

Conversion approach, a decomposition based on chordal completions, is routinely used for solving large-scale SDPs. We show that the SDP resulting from the conversion approach is numerically degenerate under very mild assumptions. Numerical experiments on SDPLIB are provided to demonstrate the impact on solvers such as SDPT3 and SeDuMi.

We propose a new formulation for the MCCP which does not rely on finding perfect elimination orderings of the graph, as has been considered in previous work. We introduce several families of facet-defining inequalities for cycle subgraphs. Numerical studies combining heuristic separation methods based on a threshold rounding and lazy-constraint generation indicate that our approach substantially outperforms existing methods for the MCCP, solving many benchmark graphs to optimality for the first time.

Biography. Arvind Raghunathan is a Senior Principal Scientist at Mitsubishi Electric Research Laboratories (MERL). His research interests are in the development of algorithms for the solution of nonlinear and mixed integer programming problems with applications in electric grid operations, model predictive control, and transportation. Arvind’s research has found business impact in Mitsubishi’s products and has won top technical honors within MERL and Mitsubishi Electric Corporation. Arvind currently serves as an associate editor for Optimization & Engineering journal and as an expert of ANSI on the ISO Working Group on Smart Transportation. He obtained a Ph.D. from Carnegie Mellon University and a B.Tech from Indian Institute of Technology (Madras) both in Chemical Engineering. He worked for United Technologies Research Center for 7 years prior to joining MERL.