Polyhedral Outer Approximations in Convex Mixed-Integer Nonlinear Programming

Abstract

This thesis is focused on a specific type of optimization problems commonly referred to as convex MINLP problems. The goal has been to investigate and develop efficient methods for solving such optimization problems. The thesis focuses on decompositionbased algorithms in which a polyhedral outer approximation is used for approximating the integer relaxed feasible set. An introduction and summary of different types of optimization problems are given in Chapter 2, and a summary of work previously done within the field is given in Chapter 3. The thesis is written as a collection of articles, and the results presented in the papers are summarized in Chapter 4. Different approaches for constructing and utilizing polyhedral outer approximations are presented and analyzed within the thesis. An algorithm, called the extended supporting hyperplane (ESH) algorithm, which uses supporting hyperplanes to the integer relaxed feasible set to construct the polyhedral approximation is presented. The ESH algorithm is utilized in a new solver, called SHOT, which is described in the thesis and presented in detail in the enclosed papers. Different techniques for utilizing the polyhedral approximations are presented in the thesis, and numerical test verifies their efficiency. Reformulation techniques for utilizing separability of the nonlinear functions to construct tighter approximations are also described and analyzed.