Paperlane

no. 6 · Monday 2 November 2026

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations

Katherine Charbonneau, Hao Hu and Renata Sotirov

math.OC · 50 pp

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.

comments
50 pages, including 32 pages of supplementary numerical results
fields
Optimization and Control
pdf ↗ page arXiv:2610.41051 ↗