TY - JOUR

T1 - Reformulations for utilizing separability when solving convex MINLP problems

AU - Kronqvist, Jan

AU - Lundell, Andreas

AU - Westerlund, Tapio

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Convex MINLP

KW - Lifted polyhedral approximation

KW - Separable MINLP

KW - Extended supporting hyperplane algorithm

KW - Outer approximation

KW - extended cutting plane algorithm

KW - Convex MINLP

KW - Lifted polyhedral approximation

KW - Separable MINLP

KW - Extended supporting hyperplane algorithm

KW - Outer approximation

KW - extended cutting plane algorithm

KW - Convex MINLP

KW - Lifted polyhedral approximation

KW - Separable MINLP

KW - Extended supporting hyperplane algorithm

KW - Outer approximation

KW - extended cutting plane algorithm

U2 - 10.1007/s10898-018-0616-3

DO - 10.1007/s10898-018-0616-3

M3 - Artikel

SN - 0925-5001

VL - 71

SP - 571

EP - 592

JO - Journal of Global Optimization

JF - Journal of Global Optimization

IS - 3

ER -