On the Minimum Chordal Completion Polytope

David Bergman (), Carlos H. Cardonha (), Andre A. Cire () and Arvind U. Raghunathan ()
Additional contact information
David Bergman: Operations and Information Management, University of Connecticut, Storrs, Connecticut 06260;
Carlos H. Cardonha: IBM Research, São Paulo 04007-900, Brazil;
Andre A. Cire: Department of Management, University of Toronto Scarborough and Rotman School of Management, Toronto, Ontario M1E-1A4, Canada;
Arvind U. Raghunathan: Mitsubishi Electric Research Labs, Cambridge, Massachusetts 02139

Operations Research, 2019, vol. 67, issue 2, 532-547

Abstract: A graph is chordal if every cycle with at least four edges contains a chord —that is, an edge connecting two nonconsecutive vertices of the cycle. Several classical applications in sparse linear systems, database management, computer vision, and semidefinite programming can be reduced to finding the minimum number of edges to add to a graph so that it becomes chordal, known as the minimum chordal completion problem (MCCP). We propose a new formulation for the MCCP that 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 and investigate the underlying separation problems, showing that some key inequalities are NP-hard to separate. We also identify conditions through which facets and inequalities associated with the polytope of a certain graph can be adapted in order to become facet defining for some of its subgraphs or supergraphs. Numerical studies combining heuristic separation methods and lazy-constraint generation indicate that our approach substantially outperforms existing methods for the MCCP.

Keywords: networks/graphs; applications: networks/graphs; programming: integer; algoritms: cutting plane/facet (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2018.1783 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:67:y:2019:i:2:p:532-547

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().