EURO 2025 Leeds
Abstract Submission

1115. New Family of cutting planes for 0-1 polynomials programming problem: RTL-K to RLT-1 cutting planes

Invited abstract in session MB-20: Integer Programming and Combinatorial Optimization: Complexity Questions and Algorithms, stream Combinatorial Optimization.

Monday, 10:30-12:00
Room: Esther Simpson 2.11

Authors (first author is the speaker)

1. Ibrahim Dan Dije
AOTI, UQAM
2. Franklin Djeumou Fomeni
AOTI, University of Quebec in Montreal
3. Leandro Coelho
Operations and Decision Systems, Université Laval

Abstract

The reformulation-linearization technique (RLT), due to Sherali and Adams, is a general framework for constructing hierarchies of linear programming (LP) relaxations of various optimization problems. It was first developed for 0-1 polynomial programs, but was soon adapted to continuous polynomial programs, and then extended to mixed 0-1 polynomial programs. Since then, it has been further extended and adapted, to cover a wide range of integer programming and global optimization problems. As one moves up the levels of the RLT hierarchy, the LP relaxations grow stronger, also the number of variables increases exponentially. In practice, therefore, one can hope to solve the relaxations only at very low levels of the hierarchy. In fact, even solving the relaxation at the level two can be challenging.

In this talk, we present a framework which generalizes quadratic space cutting planes from any given hierarchy level, by weakening the higher-level inequalities to quadratic space ones with a direct jump moving by using set subdivision. The estimators obtained from the weakening represent facets to the convex hull of the high-level multilinear monomials.

We test the generated cutting planes using instances of the quadratic knapsack problem, then we will present some computational results which show that these cutting planes improved the linear relaxation of the quadratic knapsack problem.

Keywords

Status: accepted

Back to the list of papers