Metraipolis › archive › dc_64eb37d930ce

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations — arXiv:2610.41051

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.41051
License (as archived): CC0-1.0
Archived: 2026-11-02T07:56:27.506Z
SHA-256 of the archived text: 13e2faec21ac041be876bcd3b544f6fdffbeec093193836f12631bbf3aab6493
Stable URL of this page: https://metraipolis.com/documento/dc_64eb37d930ce

How to cite

Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations — arXiv:2610.41051 — arXiv (en), https://arxiv.org/abs/2610.41051 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_64eb37d930ce (Metraipolis archive dc_64eb37d930ce, sha256 13e2faec21ac041be876bcd3b544f6fdffbeec093193836f12631bbf3aab6493)

BibTeX

@misc{dc64eb37d930ce,
  title = {Box-Cone Representations of Bound-Factor RLT Constraints in Semidefinite Relaxations — arXiv:2610.41051},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41051},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_64eb37d930ce; sha256 13e2faec21ac041be876bcd3b544f6fdffbeec093193836f12631bbf3aab6493},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41051. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2610.41051 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:41:45.690Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).