integer semidefinite programming

Spanning and Splitting: Integer Semidefinite Programming for the Quadratic Minimum Spanning Tree Problem

  • Frank de Meijer
  • Melanie Siebenhofer
  • Renata Sotirov
  • Angelika Wiegele
    • Categories (Mixed) Integer Nonlinear Programming, Network Optimization, Semi-definite Programming Tags , , , ,

    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. We present a formulation of the QMSTP as a mixed-integer semidefinite program exploiting the algebraic connectivity of a graph. Based on this formulation, we derive a doubly nonnegative relaxation … Read more

    The Chvátal-Gomory Procedure for Integer SDPs with Applications in Combinatorial Optimization

  • Frank de Meijer
  • Renata Sotirov
    • Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Semi-definite Programming Tags , , , ,

    In this paper we study the well-known Chvátal-Gomory (CG) procedure for the class of integer semidefinite programs (ISDPs). We prove several results regarding the hierarchy of relaxations obtained by iterating this procedure. We also study different formulations of the elementary closure of spectrahedra. A polyhedral description of the elementary closure for a specific type of … Read more