Forest Characterization of When SDP-RLT Strengthens RLT for Bilinear Terms

Abstract

We study two relaxations for bilinear terms in box-constrained variables: the reformulation-linearization technique (RLT) relaxation and the SDP-RLT relaxation, which combines RLT with semidefinite programming (SDP). We represent the pattern of bilinear terms by an undirected graph, with one vertex for each variable and one edge for each bilinear term. A point feasible for the RLT relaxation fixes only part of the lifted matrix of the SDP-RLT relaxation, leaving the remaining entries to be chosen subject to the diagonal RLT inequalities, and the two relaxations differ exactly when these entries cannot always be chosen so that the matrix becomes positive semidefinite. Formulating this as a positive semidefinite matrix completion problem, we show that the feasible regions of the two relaxations coincide if and only if the graph is a forest. We also measure how large the difference can be when the graph contains a complete bipartite subgraph: a bilinear objective given by a Hadamard matrix yields optimal values whose ratio grows with the size of that subgraph.

On convex envelopes of bilinear terms over polygonal domains
Adrian Göß, Jan Krause, Martina Kuchlbauer +1
arXiv29 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
Characterization of tree-child networks in terms of mu vectors
Toni Fuentes, Vincent Moulton, Katharina T. Huber +1
arXiv21 Sep 2026PreprintCC BY-NC-SA 4.0Full textEvolutionary biology Combinatorics & discrete mathematicsarXiv
Characterization of C^1,α-domains in terms of Carleson-type ε-coefficients
Xavier Tolsa, Tobias Wang
arXiv14 Oct 2026PreprintCC BY 4.0Full textAnalysis & PDEsarXiv
Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications
Yusuke Aikawa, Keita Ishizuka, Tomoki Moriya
arXiv1 Nov 2026PreprintarXiv licenceFull textGeneral mathematicsarXiv
When are dividend barriers optimal? A distributional characterization in renewal risk models
Linyu Miao
arXiv1 Nov 2026PreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeX RIS

BibTeX

@misc{watanabe2026forest,
  title = {{Forest Characterization of When SDP-RLT Strengthens RLT for Bilinear Terms}},
  author = {Hayato Watanabe and Takami Sato and Kazuhide Nakata and Ken Kobayashi},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.27727},
  eprint = {2610.27727},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.27727},
}

RIS

TY  - UNPB
TI  - Forest Characterization of When SDP-RLT Strengthens RLT for Bilinear Terms
AU  - Hayato Watanabe
AU  - Takami Sato
AU  - Kazuhide Nakata
AU  - Ken Kobayashi
PY  - 2026
DA  - 2026/10/20
PB  - arXiv
DO  - 10.48550/arxiv.2610.27727
UR  - https://arxiv.org/abs/2610.27727
AB  - We study two relaxations for bilinear terms in box-constrained variables: the reformulation-linearization technique (RLT) relaxation and the SDP-RLT relaxation, which combines RLT with semidefinite programming (SDP). We represent the pattern of bilinear terms by an undirected graph, with one vertex for each variable and one edge for each bilinear term. A point feasible for the RLT relaxation fixes only part of the lifted matrix of the SDP-RLT relaxation, leaving the remaining entries to be chosen subject to the diagonal RLT inequalities, and the two relaxations differ exactly when these entries cannot always be chosen so that the matrix becomes positive semidefinite. Formulating this as a positive semidefinite matrix completion problem, we show that the feasible regions of the two relaxations coincide if and only if the graph is a forest. We also measure how large the difference can be when the graph contains a complete bipartite subgraph: a bilinear objective given by a Hadamard matrix yields optimal values whose ratio grows with the size of that subgraph.
ER  -

Abstract

Related

Cite