In multi-objective mixed-integer convex optimization multiple convex objective functions need to be optimized simultaneously while some of the variables are only allowed 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 a decision space based method from the literature and show that much larger instances can be solved with our new algorithm.
Citation
Eichfelder, G., Warnow, L. A hybrid patch decomposition approach to compute an enclosure for multi-objective mixed-integer convex optimization problems. Math Meth Oper Res (2023). https://doi.org/10.1007/s00186-023-00828-x