A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems
Open Access
- 2 August 2023
- journal article
- research article
- Published by Springer Nature in Mathematical Methods of Operations Research
- Vol. 100 (1) , 291-320
Abstract
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.Keywords
Funding Information
- Technische Universität Ilmenau
This publication has 25 references indexed in Scilit:
- Optimal allocation of water to competing stakeholders in a shared watershedAnnals of Operations Research, 2015
- An Exact Algorithm for Finding Extreme Supported Nondominated Points of Multiobjective Mixed Integer ProgramsManagement Science, 2010
- Equity portfolio construction and selection using multiobjective mathematical programmingJournal of Global Optimization, 2009
- An algorithmic framework for convex mixed integer nonlinear programsDiscrete Optimization, 2008
- Bound sets for biobjective combinatorial optimization problemsComputers & Operations Research, 2007
- Approximation Methods in Multiobjective ProgrammingJournal of Optimization Theory and Applications, 2005
- On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programmingMathematical Programming, 2005
- INTLAB — INTerval LABoratory1999
- Solving mixed integer nonlinear programs by outer approximationMathematical Programming, 1994
- Scalarizing vector optimization problemsJournal of Optimization Theory and Applications, 1984