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

Spanish

Estudiamos dos relajaciones para términos bilíneos en variables confinadas en caja: la técnica de reformulación-linearización (RLT) y la relajación SDP-RLT, que combina el RLT con la programación semidefinida (SDP). Representamos el patrón de términos bilíneos por un gráfico no direccionado, con un vértice para cada variable y un borde para cada término bilíneo. Un punto factible para la relajación RLT fija solo parte de la matriz elevada de la relajación SDP-RLT, dejando que las entradas restantes sean elegidas sujetas a las desigualdades RLT diagonales, y las dos relajaciones difieren exactamente cuando estas entradas no siempre se pueden elegir para que la matriz se convierta en semidefinida positiva. Formulando esto como un problema

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