On Integrality in Semidefinite Programming for Discrete Optimization

DOI10.1137/23m1580905arXiv2306.09865MaRDI QIDQ6130544

Frank de Meijer, Renata Sotirov

Publication date: 3 April 2024

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2306.09865

zbMATH Keywords

association schemesbinary quadratic programmingquadratic matrix programmingmixed-integer semidefinite programmingdiscrete positive semidefinite matrices

Mathematics Subject Classification ID

Semidefinite programming (90C22) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global optimization of robust truss topology via mixed integer semidefinite programming
• Unifying semidefinite and set-copositive relaxations of binary problems and randomization techniques
• Binary positive semidefinite matrices and associated integer polytopes
• Facets of the clique partitioning polytope
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• The capacitated max \(k\)-cut problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Geometric algorithms and combinatorial optimization
• Connection between semidefinite relaxations of the max-cut and stable set problems
• Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem
• Projection results for the \(k\)-partition problem
• Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
• A new branch and bound method for a discrete truss topology design problem
• A branch-and-cut algorithm for solving mixed-integer semidefinite optimization problems
• Sparse learning via Boolean relaxations
• The partition problem
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the complete set packing and set partitioning polytopes: properties and rank 1 facets
• On Lagrangian Relaxation of Quadratic Matrix Constraints
• Relaxations of Combinatorial Problems Via Association Schemes
• A Low-Dimensional Semidefinite Relaxation for the Quadratic Assignment Problem
• On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming
• Assignment Problems and the Location of Economic Activities
• Assignment Problems
• New Code Upper Bounds From the Terwilliger Algebra and Semidefinite Programming
• Semidefinite Relaxations for Integer Programming
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• On Semidefinite Programming Relaxations of the Traveling Salesman Problem
• A comparison of the Delsarte and Lovász bounds
• The clique partitioning problem: Facets and patching facets
• A framework for solving mixed-integer semidefinite programs
• Fixing Variables in Semidefinite Relaxations
• The Maximum k-Colorable Subgraph Problem and Related Problems
• Quadratic Matrix Programming
• Handling symmetries in mixed-integer semidefinite programs

This page was built for publication: On Integrality in Semidefinite Programming for Discrete Optimization