Continuous optimization methods for convex mixed-integer nonlinear programming

Abstract

The topic of this dissertation is the design of fast branch-and-bound algorithms that use intelligently adapted approaches from continuous optimization for solving convex mixed-integer nonlinear programming problems. This class of optimization problems is NP-hard and polynomial-time algorithms for these problems are therefore unlikely to exist (unless P=NP). The importance of this class is highlighted by the fact that many real-world applications can be modeled as a (convex) mixed-integer nonlinear programming problem. Currently, there are several standard techniques such as outer approximation that are used within recent state-of-the-art software. Although all these algorithms include sophisticated improvements such as primal heuristics and effective preprocessing, they do not take into account the large gap between the algorithmic performance of NLP and IP solvers. While NLP solvers are well-engineered for large-scale problems, MIP problems of similar sizes are by far harder to solve in practice. Therefore, when using NLP techniques within MIP solvers, these NLP algorithms have to be adjusted to handle small-size instances effectively.

Taking this problem into account, we present three branch-and-bound algorithms, based on a former work by Buchheim et al. (2012) on unconstrained convex quadratic integer programming problems. The main strategies used within this branch-andbound framework include extensive preprocessing and fast incremental computations, aiming at a very fast enumeration of the nodes. The first algorithm we present is designed to solve convex quadratic mixed-integer programming problems with linear inequality constraints and is based on a new feasible active set algorithm applied to the dual of the continuous relaxation. This active set algorithm is tailored for the continuous problem and fully exploits its structure. Furthermore, a warmstarting procedure is used to reduce the number of active set iterations per node. The second algorithm we introduce is an approach called quadratic outer approximation for solving box-constrained convex mixed-integer nonlinear programming problems. It extends the classical outer approximation by using quadratic underestimators leading to a faster convergence in practice. Finally, the last algorithm we devise is aimed at a class of mean-risk portfolio optimization problems that can be modeled as convex mixed-integer programming problems with a single linear budget constraint. For this application we propose a branch-and-bound scheme using a modified Frank-Wolfe type algorithm to solve the node relaxations. Similarly to the branch-and-bound algorithms mentionded above we exploit the simplicity of the relaxations to enumerate the nodes as quickly as possible rather than focussing on strong dual bounds.

We implemented all three algorithms and compared their performance with several state-of-the art approaches. Our extensive computational studies show that all new approaches presented in this thesis are able to effectively solve large classes of real-world instances.