An approximation algorithm for multiobjective mixed-integer convex optimization
Open Access
- 29 July 2024
- journal article
- research article
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 100 (1) , 321-350
Abstract
In this article we introduce an algorithm that approximates the nondominated sets of multiobjective mixed-integer convex optimization problems. The algorithm constructs an inner and outer approximation of the front exploiting the convexity of the patches for problems with an arbitrary number of criteria. In the algorithm, the problem is decomposed into patches, which are multiobjective convex problems, by fixing the integer assignments. The patch problems are solved using (simplicial) Sandwiching. We identify parts of patches that are dominated by other patches and ensure that these patch parts are not refined further. We prove that the algorithm converges and show a bound on the reduction of the approximation error in the course of the algorithm. We illustrate the behaviour of our algorithm using some numerical examples and compare its performance to an algorithm from literature.Keywords
Funding Information
- Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM
This publication has 33 references indexed in Scilit:
- A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problemsMathematical Methods of Operations Research, 2023
- Rather the Rule than the Exception: Non‐Convex Pareto Sets and their Navigation in Distillation ProcessesChemie Ingenieur Technik, 2022
- Exact algorithms for multiobjective linear optimization problems with integer variables: A state of the art surveyJournal of Multi-Criteria Decision Analysis, 2022
- Interactive navigation of multiple convex patchesJournal of Multi-Criteria Decision Analysis, 2021
- Bi-objective optimisation over a set of convex sub-problemsAnnals of Operations Research, 2021
- Navigation in multiobjective optimization methodsJournal of Multi-Criteria Decision Analysis, 2016
- Primal and dual approximation algorithms for convex vector optimization problemsJournal of Global Optimization, 2014
- An approximation algorithm for convex multi-objective programming problemsJournal of Global Optimization, 2010
- Pareto navigator for interactive nonlinear multiobjective optimizationOR Spectrum, 2008
- Unbiased approximation in multicriteria optimizationMathematical Methods of Operations Research, 2003