Ambros Gleixner: Linearizing nonlinear on/off structures: perspective cuts in a global MINLP solver

Date: 2023-07-06

Time: 10:00 - 10:30

Speaker

Ambros Gleixner, Zuse institute Berlin

Abstract

The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. We provide a first, detailed computational study of perspective cuts within an LP-based branch-and-cut solver or general MINLPs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time. This is joint work with Ksenia Bestuzheva and Stefan Vigerske.