Reformulations for utilizing separability when solving convex MINLP problems

Jan Kronqvist (), Andreas Lundell and Tapio Westerlund
Additional contact information
Jan Kronqvist: Åbo Akademi University
Andreas Lundell: Åbo Akademi University
Tapio Westerlund: Åbo Akademi University

Journal of Global Optimization, 2018, vol. 71, issue 3, No 9, 592 pages

Abstract: Abstract Several deterministic methods for convex mixed integer nonlinear programming generate a polyhedral approximation of the feasible region, and utilize this approximation to obtain trial solutions. Such methods are, e.g., outer approximation, the extended cutting plane method and the extended supporting hyperplane method. In order to obtain the optimal solution and verify global optimality, these methods often require a quite accurate polyhedral approximation. In case the nonlinear functions are convex and separable to some extent, it is possible to obtain a tighter approximation by using a lifted polyhedral approximation, which can be achieved by reformulating the problem. We prove that under mild assumptions, it is possible to obtain tighter linear approximations for a type of functions referred to as almost additively separable. Here it is also shown that solvers, by a simple reformulation, can benefit from the tighter approximation, and a numerical comparison demonstrates the potential of the reformulation. The reformulation technique can also be combined with other known transformations to make it applicable to some nonseparable convex functions. By using a power transform and a logarithmic transform the reformulation technique can for example be applied to p-norms and some convex signomial functions, and the benefits of combining these transforms with the reformulation technique are illustrated with some numerical examples.

Keywords: Convex MINLP; Lifted polyhedral approximation; Separable MINLP; Extended cutting plane algorithm; Extended supporting hyperplane algorithm; Outer approximation (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-018-0616-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:71:y:2018:i:3:d:10.1007_s10898-018-0616-3

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-018-0616-3

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().