Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations
Abstract
Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable and its complement and linearizing the resulting products. Our key observation is that all products generated by one inequality share a common slack and admit an exact representation in the standard cone over the unit box. This box-cone representation processes the inequalities through independent explicit projections, without introducing a separate nonnegative slack for each scalar RLT inequality. We illustrate the computational use of the representation within standard two-block alternating direction method of multipliers (ADMM). The resulting subproblems require linear solves with a reusable factorization and explicit cone projections, without enlarging the semidefinite matrix. Experiments on 257 binary quadratic programs compare this implementation with SDPNAL+. A second application groups Max-Cut triangle inequalities into box cones and uses the resulting bounds within an existing branch-and-bound framework. Tests on 220 graphs show competitive performance with MADAM using only triangle cuts. Together, these applications illustrate the representation's usefulness as a building block for first-order methods.
Related
- Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
- Exact Convex Reformulations of Binary Quadratic Programs from Facially Reduced Semidefinite Relaxations
- Facets of nondegeneracy: central type factor groups, Heisenberg representations and Hadamard matrices
- Multiple representations in difference sets under polynomial density constraints
- Representations of Bound Quivers over 𝔽1 and Hall Algebras
BibTeX
@misc{charbonneau2026boxcone,
title = {{Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations}},
author = {Katherine Charbonneau and Hao Hu and Renata Sotirov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41051},
eprint = {2610.41051},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41051},
}
RIS
TY - UNPB
TI - Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations
AU - Katherine Charbonneau
AU - Hao Hu
AU - Renata Sotirov
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.41051
UR - https://arxiv.org/abs/2610.41051
AB - Linear inequalities can generate large constraint systems in semidefinite relaxations of binary quadratic programs, making the quadratic subproblems of splitting methods expensive to solve. We develop a box-cone representation of bound-factor reformulation-linearization technique (RLT) constraints in semidefinite relaxations of binary quadratic programs. These constraints arise by multiplying each original linear inequality by every binary variable and its complement and linearizing the resulting products. Our key observation is that all products generated by one inequality share a common slack and admit an exact representation in the standard cone over the unit box. This box-cone representation processes the inequalities through independent explicit projections, without introducing a separate nonnegative slack for each scalar RLT inequality. We illustrate the computational use of the representation within standard two-block alternating direction method of multipliers (ADMM). The resulting subproblems require linear solves with a reusable factorization and explicit cone projections, without enlarging the semidefinite matrix. Experiments on 257 binary quadratic programs compare this implementation with SDPNAL+. A second application groups Max-Cut triangle inequalities into box cones and uses the resulting bounds within an existing branch-and-bound framework. Tests on 220 graphs show competitive performance with MADAM using only triangle cuts. Together, these applications illustrate the representation's usefulness as a building block for first-order methods.
ER -