Efficient Separation of RLT Cuts for Implicit and Explicit Bilinear Products
Authors:
- Ksenia BestuzhevaKBKsenia Bestuzheva
- Ambros GleixnerAGAmbros Gleixner
- Tobias AchterbergTATobias Achterberg
Preprint
Abstract
The reformulation-linearization technique (RLT) is a prominent approach to constructing tight linear relaxations of non-convex continuous and mixed-integer optimization problems. The goal of this paper is to extend the applicability and improve the performance of RLT for bilinear product relations. First, a method for detecting bilinear product relations implicitly contained in mixed-integer linear programs is developed based on analyzing linear constraints with binary variables, thus enabling the application of bilinear RLT to a new class of problems. Our second contribution addresses the high computational cost of RLT cut separation, which presents one of the major difficulties in applying RLT efficiently in practice. We propose a new RLT cutting plane separation algorithm which identifies combinations of linear constraints and bound factors that are expected to yield an inequality that is violated by the current relaxation solution. A detailed computational study based on implementations in two solvers evaluates the performance impact of the proposed methods.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming libraryMathematical Programming Computation, 2021
- Optimal power flow: a bibliographic survey IEnergy Systems, 2012
- Optimal power flow: a bibliographic survey IIEnergy Systems, 2012
- Reduced RLT representations for nonconvex polynomial programming problemsJournal of Global Optimization, 2011
- Linearity Embedded in Nonconvex ProgramsJournal of Global Optimization, 2005
- Reformulation and convex relaxation techniques for global optimization4OR, 2004
- Mixed-integer bilinear programming problemsMathematical Programming, 1993
- A new reformulation-linearization technique for bilinear programming problemsJournal of Global Optimization, 1992
- A global optimization algorithm for polynomial programming problems using a Reformulation-Linearization TechniqueJournal of Global Optimization, 1992
- Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problemsMathematical Programming, 1976