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

Arabic

ونحن ندرس اثنين من الاسترخاءات للمادة الثنائية في المتغيرات المحددة من القسم: تقنية الاسترخاء-التنظيمية (RLT) واسترخاء SDP-RLT، الذي يجمع RLT مع التخطيط المحدد (SDP). نحن نعتبر نموذجاً للمادة الثنائية من قبل نموذج غير المحدد، مع نقطة تحول واحدة لكل المتغيرات وقطر واحد لكل نموذج ثنائي. يحدد نقطة ممكنة للالتفاف على RLT فقط جزءاً من نموذج الاسترخاء المحدد من SDP-RLT، مما يجعله ينبغي أن يختار الملفات المتبقية على أساس عدم المساواة المحددة من RLT المحدد، ونحن نعتبر الترخيصات المتبقية مختلفة تماما

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