Newest papers

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

Hayato Watanabe, Takami Sato, Kazuhide Nakata, Ken Kobayashi · 2026 · arXiv (Cornell University)

DOI: 10.48550/arxiv.2610.27727 · cited by 0 works (OpenAlex) · open-access PDF

Portuguese

Estudamos duas relaxações para termos bilineares em variáveis limitadas por caixa: a técnica de reformulação-linearização (RLT) e a relaxação SDP-RLT, que combina RLT com programação semidefinida (SDP). Nós representamos o padrão de termos bilineares por um gráfico não-direcionado, com um topo para cada variável e um limite para cada termo bilinear. Um ponto viável para a relaxação RLT fixa apenas parte da matriz levantada da relaxação SDP-RLT, deixando as entradas restantes a serem escolhidas sujeitas às desigualdades RLT diagonais, e as duas relaxações diferem exatamente quando essas entradas não podem ser sempre escolhidas para que a matriz se torne semidefinida positiva. Formulando isso como um problema de conclusão

Machine translation (Meta M2M100); the English original follows.

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.

Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese

Topics: Mathematics, Bilinear interpolation, Combinatorics, Vertex (graph theory), Bipartite graph, Semidefinite programming

Sources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange