Robust Multi-Objective Optimization: Analysis and Approaches

• Applicant: Professorin Dr. Anita Schöbel
• Subject Area: Mathematics ; Theoretical Computer Science
• Term: from 2019 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 426002582

• Final Report Year: 2023

Final Report Abstract

Optimization problems that arise in industry and society are almost always characterized by different objectives and uncertainties. In transport, for example, the aim is to minimize travel times, costs and CO2 emissions. Future demand and the development of fuel prices, among other things, are uncertain. Such problems fall into the field of robust multi-objective optimization. It has emerged over the last 15 years in which various concepts for defining a “robust Pareto” solution have been developed. However, algorithms for finding such solutions and theoretical results on their properties are still scarce. In this project, we successfully extended the theory for robust multi-objective optimization. We were also able to develop practical solution methods for the resulting problems. On a theoretical level, set-theoretical concepts were used to evaluate the various existing concepts and to identify their different properties. The intuition that so-called lightly robustly efficient solutions represent a good compromise between minmax robustly efficient solutions and the nominal solutions was analytically confirmed for the first time. We also defined a “price” of multi-objective robustness and showed how it can be used in practice. In another paper, we were able to transfer the concept of the robustness gap to multi-objective problems and to estimate this gap theoretically and algorithmically by providing upper and lower bounds. The solution methods we have developed combine methods from robust and from multiobjective optimization in two different approaches. In the first approach, the problem is interpreted as a multi-objective problem with an objective function that includes maximization with respect to uncertainty. This leads to a further development of the well-known dichotomic search method. In the second approach, the problem is instead interpreted as a robust problem and a cutting plane method is applied to it. To this end, the cutting plane method, known from robust optimization, needs to be generalized to multi-objective problems. In addition, we develop an approach based on duality theory in the case of problems that are linear in the scenario. All three methods were implemented and compared experimentally. In order to deal with applications we tested the procedures on integer optimization problems. Furthermore, a portfolio problem was analyzed and investigated using our approaches. In addition, various relationships to set-valued optimization emerged, which were used both in the evaluation of robust efficient solution sets and in the development of bounds for the cutting plane method.

Publications

• On the p-hub interdiction problem. Computers & Operations Research, 124, 105056.
  Ullmert, Thomas; Ruzika, Stefan & Schöbel, Anita
  
• The price of multiobjective robustness: Analyzing solution sets to uncertain multiobjective problems. European Journal of Operational Research, 291(2), 782-793.
  Schöbel, Anita & Zhou-Kangas, Yue
  
• The point-based robustness gap for uncertain multiobjective optimization. Optimization, 73(6), 1897-1931.
  Krüger, Corinna; Schöbel, Anita; Fritzen, Lena & Wiecek, Margaret M.
  
• “Recoverable Robust Periodic Timetabling”. In: 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems 115 (2023), pp. 9:1–9:16.
  V. Grafe & A. Schöbel
  
• Approaches for biobjective integer linear robust optimization. European Journal of Operational Research.
  Chlumsky-Harttmann, Fabian; Schmidt, Marie & Schöbel, Anita