Multiobjective combinatorial optimization in higher dimensions

• Applicant: Professorin Dr. Kathrin Klamroth
• Subject Area: Mathematics
• Term: from 2020 to 2025
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 441310140

• Final Report Year: 2025

Final Report Abstract

Multi-objective combinatorial optimization (MOCO) is a quickly growing field that is highly relevant for a multitude of application areas and at the same time highly challenging due to its inherent complexity. Conflicting objective functions occur, for example, when balancing between economical and ecological goals in economic applications, or when compromising between quality and cost in engineering design. Typical examples of MOCO problems include multi-objective knapsack problems with applications such as capital budgeting, multi-objective assignment problems, multi-objective facility location problems, and network problems like multi-objective minimum spanning tree, shortest path, minimum cost flow and traveling salesman problems. Application areas include traffic planning, transportation and logistics, resource scheduling, communication models, and problems in location planning, among many others. The number of considered objective functions is a main driver for the complexity of multi-objective combinatorial optimization problems. While the Pareto front can be completely ordered for bi-objective problems – if the first objective function increases, the second decreases and vice versa – this is no longer possible with three or more objective functions. Simultaneously with the drastically increasing cardinalty of the Pareto set, its description gets more and more complex. In this project, the geometric and combinatorial structure of the Pareto set is used to achieve significant progress both on a theoretical and algorithmic level. This includes the determination of representative candidate sets as well as the further development of multi-objective branch and bound methods and the analysis of different preference structures and quality measures.

Publications

• Ordinal costs in multi-objective combinatorial optimization. PhD thesis. University of Wuppertal
  J. Sudhoff
  
• DefiningPointAlgorithm
  K. Dachert, T. Fleuren & K. Klamroth
  
• Multi-objective matroid optimization with ordinal weights. Discrete Applied Mathematics, 335, 104-119.
  Klamroth, Kathrin; Stiglmayr, Michael & Sudhoff, Julia
  
• Ordinal optimization through multi-objective reformulation. European Journal of Operational Research, 311(2), 427-443.
  Klamroth, Kathrin; Stiglmayr, Michael & Sudhoff, Julia
  
• Theoretical Aspects of Subset Selection in Multi-Objective Optimisation. Natural Computing Series, 213-239. Springer International Publishing.
  Guerreiro, Andreia P.; Klamroth, Kathrin & Fonseca, Carlos M.
  
• A simple, efficient and versatile objective space algorithm for multiobjective integer programming. Mathematical Methods of Operations Research, 100(1), 351-384.
  Dächert, Kerstin; Fleuren, Tino & Klamroth, Kathrin
  
• Augmenting bi-objective branch and bound by scalarization-based information. Mathematical Methods of Operations Research, 100(1), 85-121.
  Bauß, Julius & Stiglmayr, Michael
  
• On improvements of multi-objective branch and bound. EURO Journal on Computational Optimization, 12, 100099.
  Bauß, Julius; Parragh, Sophie N. & Stiglmayr, Michael
  
• On Improvements of Multi-objective Branch and Bound. PhD thesis. University of Wuppertal
  J. Bauß
  
• A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization. Computers & Operations Research, 183, 107140.
  Lopes, Gonçalo; Klamroth, Kathrin & Paquete, Luís
  
• An output-polynomial time algorithm to determine all supported efficient solutions for multi-objective integer network flow problems. Discrete Applied Mathematics, 376, 1-14.
  Könen, David & Stiglmayr, Michael
  
• On Supportedness in Multi‐Objective Integer Linear Programming. Journal of Multi-Criteria Decision Analysis, 32(3).
  Könen, David & Stiglmayr, Michael
  
• “On Multi-objective Integer Network Flow Problems”. submitted. PhD thesis. University of Wuppertal
  D. Konen
  
• Output-sensitive complexity of multi-objective integer network flow problems. Journal of Combinatorial Optimization, 51(2).
  Könen, David & Stiglmayr, Michael