Optimization Online


Binary positive semidefinite matrices and associated integer polytopes

Adam Letchford (a.n.letchford***at***lancaster.ac.uk)
Michael Soerensen (mim***at***asb.dk)

Abstract: We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature -- the cut, boolean quadric, multicut and clique partitioning polytopes -- are faces of binary psd polytopes. Finally, we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.

Keywords: polyhedral combinatorics, semidefinite programming, max-cut problem

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: A.N. Letchford & M.M. Sørensen (2012) Binary positive semidefinite matrices and associated integer polytopes. Math. Program., 131(1), 253-271.


Entry Submitted: 12/16/2009
Entry Accepted: 12/16/2009
Entry Last Modified: 02/29/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society