On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems

In this thesis we focus on solution methods for convex mixed-integer nonlinear optimization problems (MINLP). As one main result, we propose a new algorithm guaranteeing global optimality for convex MINLPs under standard assumptions. The new algorithm called MIQP-supported outer approximation (MIQPSOA) incorporates the successive solution of convex mixed-integer quadratic programs (MIQP) in a linear outer approximation framework. An extensive numerical competitive study based on several different MINLP solvers shows, that a first implementation of the new method performs well in terms of both the reliability and the efficiency. Since the new method is designed to solve simulation-based optimization problems arising in practical engineering applications, the main performance criterion is the number of function evaluations required to solve a problem. Furthermore, the test results indicate, that the integration of mixed-integer search steps, resulting from the solution of convex MIQPs, significantly improves the reliability and the efficiency compared to well-known linear outer approximation methods. After reviewing available solution techniques for convex MINLP problems, we present the algorithmic set-up as well as the convergence proof of MIQPSOA. As pointed out in this dissertation, MIQPSOA is a first step towards a convergent MINLP solution method, that solely relies on the successive solution of convex MIQPs as proposed by Exler and Schittkowski. Finally, we present an extensive numerical test case study considering different solution methods for convex MINLPs. The second part of this thesis deals with efficient solution techniques for convex mixed-integer quadratic programs, that arise as subproblems during the solution of MINLPs by MIQP-based algorithms, such as MIQPSOA. First, we briefly review latest developments in state-of-the-art mixed-integer linear (MILP) solvers, since we want to develop a MIQP solver that incorporates the most successful components of MILP solvers. As we focus on branch-and-bound methods, one main component is an efficient and robust sub-solver for continuous quadratic programs, which is able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs. Extensive numerical tests show, that the performance of a branch-and-bound solver can be significantly increased by exploiting warmstarts. Furthermore, it turns out, that in a majority of the test cases, where disjunctive cutting planes exist, the calculation times are reduced up to a factor of more than 5. Nevertheless there are also instances, where the presents of disjunctive cutting planes significantly slows down the performance. Due to the efficient cut generation method developed within this thesis, the generation of cutting planes has almost no influence on the calculation time, if no disjunctive cuts exist, which is the case in about 45 \% of all test instances. As a consequence, the application of cutting planes for MIQPs needs further attention and especially a dynamic cut management might be very profitable. Finally, we compare the performance of our branch-and-cut solver MIQL with the solver SCIP, which is one of the state-of-the-art MILP solvers, that can also solve MIQPs. These tests indicate, that MIQL outperforms SCIP on hard MIQP instances, while SCIP is faster for simpler test cases.

Level thesis:degree_level

thesis.doctoral

Grantor dc:publisher

Universität Bayreuth

Year

2013

Author dc:creator

• Lehmann, Thomas

Contributors dc:contributor

• Schittkowski, Klaus

Repository record source_url

https://epub.uni-bayreuth.de/id/eprint/131/

OAI identifier oai:identifier

oai:epub.uni-bayreuth.de:131