Polyhedral Outer Approximations in Convex Mixed-Integer Nonlinear Programming

G5 Doctoral dissertation (article)


Internal Authors/Editors


Publication Details

List of Authors: Jan Kronqvist
Publisher: Åbo Akademi University
Place: Åbo
Publication year: 2018
ISBN: 978-952-12-3734-8
eISBN: 978-952-12-3735-5


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.


Keywords

convex MINLP problems, Convex optimization

Last updated on 2019-22-09 at 05:09