A solver for multiobjective mixed-integer convex and nonconvex optimization. - In: Journal of optimization theory and applications, ISSN 1573-2878, Bd. 0 (2023), 0, insges. 31 S.
This paper proposes a general framework for solving multiobjective nonconvex optimization problems, i.e., optimization problems in which multiple objective functions have to be optimized simultaneously. Thereby, the nonconvexity might come from the objective or constraint functions, or from integrality conditions for some of the variables. In particular, multiobjective mixed-integer convex and nonconvex optimization problems are covered and form the motivation of our studies. The presented algorithm is based on a branch-and-bound method in the pre-image space, a technique which was already successfully applied for continuous nonconvex multiobjective optimization. However, extending this method to the mixed-integer setting is not straightforward, in particular with regard to convergence results. More precisely, new branching rules and lower bounding procedures are needed to obtain an algorithm that is practically applicable and convergent for multiobjective mixed-integer optimization problems. Corresponding results are a main contribution of this paper. What is more, for improving the performance of this new branch-and-bound method we enhance it with two types of cuts in the image space which are based on ideas from multiobjective mixed-integer convex optimization. Those combine continuous convex relaxations with adaptive cuts for the convex hull of the mixed-integer image set, derived from supporting hyperplanes to the relaxed sets. Based on the above ingredients, the paper provides a new multiobjective mixed-integer solver for convex problems with a stopping criterion purely in the image space. What is more, for the first time a solver for multiobjective mixed-integer nonconvex optimization is presented. We provide the results of numerical tests for the new algorithm. Where possible, we compare it with existing procedures.
https://doi.org/10.1007/s10957-023-02285-2
A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems. - In: Mathematical methods of operations research, ISSN 1432-5217, Bd. 0 (2023), 0, insges. 30 S.
In multi-objective mixed-integer convex optimization, multiple convex objective functions need to be optimized simultaneously while some of the variables are restricted to take integer values. In this paper, we present a new algorithm to compute an enclosure of the nondominated set of such optimization problems. More precisely, we decompose the multi-objective mixed-integer convex optimization problem into several multi-objective continuous convex optimization problems, which we refer to as patches. We then dynamically compute and improve coverages of the nondominated sets of those patches to finally combine them to obtain an enclosure of the nondominated set of the multi-objective mixed-integer convex optimization problem. Additionally, we introduce a mechanism to reduce the number of patches that need to be considered in total. Our new algorithm is the first of its kind and guaranteed to return an enclosure of prescribed quality within a finite number of iterations. For selected numerical test instances we compare our new criterion space based approach to other algorithms from the literature and show that much larger instances can be solved with our new algorithm.
https://doi.org/10.1007/s00186-023-00828-x
A test instance generator for multiobjective mixed-integer optimization. - In: Mathematical methods of operations research, ISSN 1432-5217, Bd. 0 (2023), 0, insges. 26 S.
Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. In this paper we present a generator for test instances to evaluate solvers for multiobjective mixed-integer linear and nonlinear optimization problems. Based on test instances for purely continuous and purely integer problems with known efficient solutions and known nondominated points, suitable multiobjective mixed-integer test instances can be generated. The special structure allows to construct instances scalable in the number of variables and objective functions. Moreover, it allows to control the resulting efficient and nondominated sets as well as the number of efficient integer assignments.
https://doi.org/10.1007/s00186-023-00826-z
Advancements in the computation of enclosures for multi-objective optimization problems. - In: European journal of operational research, ISSN 0377-2217, Bd. 310 (2023), 1, S. 315-327
A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. For that computation one often makes use of so-called local upper bounds. In this paper we present a generalization of this concept. For the first time, this allows to apply a warm start strategy to the computation of an enclosure. We also show how this generalized concept allows to remove empty areas of an enclosure by deleting certain parts of the lower and upper bound sets which has not been possible in the past. We demonstrate how to apply our ideas to the box approximation algorithm, a general framework to compute an enclosure, as recently used in the solver called BAMOP. We show how that framework can be simplified and improved significantly, especially concerning its practical numerical use. In fact, we show for selected numerical instances that our new approach is up to eight times faster than the original one. Hence, our new framework is not only of theoretical but also of practical use, for instance for continuous convex or mixed-integer quadratic optimization problems.
https://doi.org/10.1016/j.ejor.2023.02.032
Convexity and continuity of specific set-valued maps and their extremal value functions. - In: Journal of applied and numerical optimization, ISSN 2562-5535, Bd. 5 (2023), 1, S. 71-92
In this paper, we study several classes of set-valued maps, which can be used in set-valued optimization and its applications, and their respective maximum and minimum value functions. The definitions of these maps are based on scalar-valued, vector-valued, and cone-valued maps. Moreover, we consider those extremal value functions which are obtained when optimizing linear functionals over the image sets of the set-valued maps. Such extremal value functions play an important role for instance for derivative concepts for set-valued maps or for algorithmic approaches in set-valued optimization. We formulate conditions under which the set-valued maps and their extremal value functions inherit properties like (Lipschitz-)continuity and convexity.
https://doi.org/10.23952/jano.5.2023.1.05
Relaxed dissipativity assumptions and a simplified algorithm for multiobjective MPC. - In: Computational optimization and applications, ISSN 1573-2894, Bd. 86 (2023), 3, S. 1081-1116
We consider nonlinear model predictive control (MPC) with multiple competing cost functions. In each step of the scheme, a multiobjective optimal control problem with a nonlinear system and terminal conditions is solved. We propose an algorithm and give performance guarantees for the resulting MPC closed loop system. Thereby, we significantly simplify the assumptions made in the literature so far by assuming strict dissipativity and the existence of a compatible terminal cost for one of the competing objective functions only. We give conditions which ensure asymptotic stability of the closed loop and, what is more, obtain performance estimates for all cost criteria. Numerical simulations on various instances illustrate our findings. The proposed algorithm requires the selection of an efficient solution in each iteration, thus we examine several selection rules and their impact on the results. and we also examine numerically how different selection rules impact the results
https://doi.org/10.1007/s10589-022-00398-4
Solving set-valued optimization problems using a multiobjective approach. - In: Optimization, ISSN 1029-4945, Bd. 72 (2023), 3, S. 789-820
Set-valued optimization using the set approach is a research topic of high interest due to its practical relevance and numerous interdependencies to other fields of optimization. However, it is a very difficult task to solve these optimization problems even for specific cases. In this paper, we study set-valued optimization problems and develop a multiobjective optimization problem that is strongly related to it. We prove that the set of weakly minimal solutions of this subproblem is closely related to the set of weakly minimal elements of the set-valued optimization problem and that these sets can get arbitrarily close in a certain sense. Subsequently, we introduce a concept of approximations of the solution set of the set-valued optimization problem. We define a quality measure in the image space that can be used to compare finite approximations of this kind and outline a procedure to enhance a given approximation. We conclude the paper with some numerical examples.
https://doi.org/10.1080/02331934.2021.1988596
Limit sets in global multiobjective optimization. - In: Optimization, ISSN 1029-4945, Bd. 0 (2022), 0, S. 1-27
Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein [A general branch-and-bound framework for continuous global multiobjective optimization. J Glob Optim. 2021;80:195-227], we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the terminal provisional nondominated set approximate the nondominated set when the termination accuracy is driven to zero. Our convergence analysis of the enclosures relies on constructions from the above paper, but is self-contained and also covers the mixed-integer case. The analysis for the provisional nondominated set is based on general convergence properties of the epsilon-nondominated set, and hence it is also applicable to other algorithms which generate such points. Furthermore, we discuss post-processing steps for the terminal enclosure and provide numerical illustrations for the cases of two and three objective functions.
https://doi.org/10.1080/02331934.2022.2092479
A vectorization scheme for nonconvex set optimization problems. - In: SIAM journal on optimization, ISSN 1095-7189, Bd. 32 (2022), 2, S. 1184-1209
In this paper, we study a solution approach for set optimization problems with respect to the lower set less relation. This approach can serve as a base for numerically solving set optimization problems by using established solvers from multiobjective optimization. Our strategy consists of deriving a parametric family of multiobjective optimization problems whose optimal solution sets approximate, in a specific sense, that of the set-valued problem with arbitrary accuracy. We also examine particular classes of set-valued mappings for which the corresponding set optimization problem is equivalent to a multiobjective optimization problem in the generated family. Surprisingly, this includes set-valued mappings with a convex graph.
https://doi.org/10.1137/21M143683X
On the exactness of the ε-constraint method for biobjective nonlinear integer programming. - In: Operations research letters, ISSN 0167-6377, Bd. 50 (2022), 3, S. 356-361
The ε-constraint method is a well-known scalarization technique used for multiobjective optimization. We explore how to properly define the step size parameter of the method in order to guarantee its exactness when dealing with biobjective nonlinear integer problems. Under specific assumptions, we prove that the number of subproblems that the method needs to address to detect the complete Pareto front is finite. We report numerical results on portfolio optimization instances built on real-world data and show a comparison with an existing criterion space algorithm.
https://doi.org/10.1016/j.orl.2022.04.007