Cutting planes for signomial programming

arXiv2212.02857MaRDI QIDQ6419682FDOQ6419682

Leo Liberti, Author name not available (Why is that?), Author name not available (Why is that?), Claudia D'Ambrosio

Publication date: 6 December 2022

Abstract: The generation of cutting planes is crucial in solving non-convex Mixed-Integer Non-linear Programming problems to $epsilon$-global optimality. In this paper, we study the signomial-term set, i.e., the graph of a signomial-term function, which arises in the extended formulation of Signomial Programming, and we show that it suffices to consider the signomial-term set as the epigraph/hypograph of the associated signomial-term function. We present a useful reformulation of the signomial-term set, written as the zero-sublevel set of the difference of two concave power functions. We propose three types of valid linear inequalities: intersection cuts and two types of outer approximation cuts. We construct signomial-term-free sets which do not contain any point of the signomial-term set in their interiors, and show that these signomial-term-free sets are maximal in the nonnegative orthant, so they yield strong intersection cuts. The two types of outer approximation cuts are linearizations of two different convex relaxations, that differ in underestimators for the concave power function over a hyper-rectangle. On the one hand, we show that the concave power function is supermodular, and construct the first convex relaxation based on the supermodular inequalities. On the other hand, we factorize the concave power function into bivariate concave power functions, and give their closed-form convex envelopes over rectangles. Then the second convex relaxation is constructed by a lift-and-project method. We implement the proposed cuts within the solver exttt{SCIP} and show that they have good performance on MINLPLib instances.

Has companion code repository: https://github.com/lidingxu/espcuts

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Nonconvex programming, global optimization (90C26) Integer programming (90C10)

This page was built for publication: Cutting planes for signomial programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419682)