Retour

G-2025-68

Approximating the strength of higher-level RLT inequalities in the first-level RLT space for polynomial 0-1 programs

, et

référence BibTeX

The reformulation-linearization technique (RLT) is a well-established framework for generating hierarchies of linear programming (LP) relaxations for a wide range of optimization problems. Despite its theoretical power, the hierarchy is rarely applied beyond the first level, mainly due to the rapid growth in the number of variables and constraints. In this work, we introduce a framework that converts cutting planes derived from higher levels of the RLT hierarchy into cutting planes that involve only the variables from the first-level space. This is achieved by weakening higher-level inequalities into quadratic-space inequalities, using estimators of multilinear monomials obtained through set partitioning. These estimators are designed so that any inequality from RLT-\(k\) (for \(k \geq 2\)) can be reformulated as a valid inequality in quadratic space, i.e., within the scope of RLT-1. We also propose a polynomial-time separation algorithm to generate such inequalities. To assess the effectiveness of our approach, we implement it with \(k=3\) on three classes of test instances: the quadratic knapsack problem, the quadratic knapsack formulation of the dispersion problem, and the standard QLIB benchmark set. Across 523 tested instances, our computational results demonstrate that the proposed method substantially reduces the gap compared to benchmark techniques in the literature.

, 26 pages

Axes de recherche

Application de recherche

Document

G2568.pdf (530 Ko)