Mixed integer nonlinear multiobjective optimization by outer approximations

点击翻译按钮获取中文摘要

The aim of the planned research is to develop a deterministic algorithmic solution procedure for multiobjective mixed integer nonlinear optimization problems (MOMIPs). Thus, we aim to solve problems which have multiple objectives and integer and continuous variables at the same time. These types of optimization problems arise in many application fields such as location or production planning, chemical engineering, finance, and manufacturing. MOMIPs combine all the difficulties of both, multiobjective optimization and mixed integer nonlinear programming, which are among the class of theoretically difficult problems (NP-complete). These problems are intrinsically nonconvex and thus require global optimization techniques. Therefore, the design of efficient solution methods is a big challenge.For problems in which both challenges occur, multiple objectives and mixed integer variables, only a very limited number of approaches exist so far and hardly any of those deliver a mathematical guarantee for the found solutions. A reason for that might be that the typical techniques from single-objective mixed integer nonlinear optimization cannot be transferred to multiple objectives easily: the typical solution approaches use the computation of decreasing upper bounds and increasing lower bounds till the difference is less than a prescribed tolerance. In multiobjective optimization, in general an infinite number of optimal values exist. Moreover, the values are elements of a higher dimensional vector space, and speaking of the best (largest) lower bound and the best (smallest) upper bound is no longer possible, as only a partial ordering in the image space is possible. Multiobjective optimization problems can be reformulated as parameter-dependent single-objective problems by so called scalarization approaches. Then the obtained single-objective mixed-integer nonlinear problems can be solved by techniques from single-objective optimization. However, this reformulation and solution would have to be done for various parameters to obtain various solutions of the MOMIP. This is time a consuming detour and does not make use of gained information. It is also an open question on how to choose the parameters suitable. We will avoid this detour of scalarization. Instead, as we will assume that all functions appearing in the MOMIP are at least convex, we will examine polyhedral relaxations to obtain lower bounds. These bounds are now sets of points. Combined with suitable upper bounds, which will also be sets of points, and a new-to-develop termination strategy, we aim for developing a numerical algorithm, which stops with a predefined quality.