Multi-objective combinatorial optimization: supportedness, representations, and integer network flows / vorgelegt von David Könen

Könen, David

This thesis is concerned with multi-objective combinatorial optimization (MOCO) problems, which involve simultaneously optimizing several conflicting objective functions over a discrete solution space. MOCO problems have attracted significant theoretical and algorithmic attention, encompassing several well-studied problem classes, including scheduling, facility location, graph partitioning, vehicle routing, and network flow problems with widespread applications in logistics, telecommunications, operations research, and various other fields. In those conflicting scenarios, no solution exists that optimizes all objectives simultaneously. In particular, one is interested in finding solutions with the property that it can only be improved with respect to one objective if at least one other objective deteriorates. Such a solution is called efficient solution or Pareto-optimal solution and its image is called nondominated vector. This thesis explores the complexities and challenges of supportedness and determining representations or the entire nondominated point set in multi-objective combinatorialoptimization, focusing mainly on multi-objective integer minimum cost flow problems (MOIMCF). The thesis starts by presenting scalarization-based algorithms for MOCO problems. It focuses on methods that decompose the overall problem into a series of scalarized single-objective subproblems, which can then be solved using available single-objective (IP-) solvers. The presented methods are generic, i.e., they are independent of specific problem structures and hence generally applicable. Various implementation strategies are examined, including choices regarding the sequence of subproblems, scalarization techniques, and decisions about computing the entire nondominated point set or a representative subset. However, MOCO and MOIMCF belong to the class of computationally intractable problems, often containing a huge set of nondominated points. This results in high computational effort, particularly for high-dimensional problems or large instances, highlighting the need for approximation techniques and alternative methods to represent the entire nondominated point set. Therefore, this thesis focuses on determining subsets of the entire nondominated point set and investigates the existence of output-polynomial time algorithms for different solution concepts in MOIMCF problems. It is well known that MOCO problems contain supported and nonsupported nondominated points, with the latter typically outnumbering the former.A key finding of this thesis is the role of supported nondominated points as high-quality representations of the complete nondominated point set in MOIMCF. Across various test instances, supported solutions consistently demonstrated superior representational quality, as measured by hypervolume ratio and coverage error. Beyond their representational advantages, the supported nondominated points are more straightforward to compute than the nonsupported ones and can serve as a foundation for two-phase methods. Despite their importance, several different inconsistent characterizations for supported efficient solutions (and supported nondominated points)are used in the literature.Through counterexamples and theoretical analysis, the thesis proves that these definitions, while being equivalent in the context of MOLP, divergein MOCO problems, yielding distinct sets of supported nondominated points with differing structural and computational properties. This emphasizes the need for precise andconsistent definitions. Hence, equivalent definitions and characterizations for supported efficient solutions are summarized, and a distinction between \emph{supported} and \emph{weakly supported} efficient solutions is introduced, which is particularly important for MOCO problems with more than two objectives. Afterwards, this thesis present an improved time complexity algorithm for the \emph{all optimal integer flow} (AOF) problem, consisting of determining all optimal integer solutions of a linear integer network flow problem, providing foundational tools for further multi-objective solution methods. The thesis further examines the computational complexity of enumerating all supported nondominated vectors for MOIMCF. It concludes that there is no output-polynomial algorithm for aMOIMCF problem with a fixed number of $p$ objectives that determines all weakly supported nondominated vectors unless $\mathbf{P} = \mathbf{NP}$. Moreover, it shows that there cannot existan output-polynomial time algorithm for the enumeration of all supported nondominatedvectors that determine the vectors in an ordered manner in the outcome space unless $\mathbf{P} = \mathbf{NP}$. In contrast, this thesis presents output-polynomial time algorithms for determiningall supported efficient solutions for BOIMCF problems and general MOIMCF problemswith a fixed number of objectives. It also proposes novel methods for identifying supported nondominated vectors in bi-objective minimum cost flow problems accompanied by a numerical comparison between decision- and objective-space methods.The numerical tests highlight that the outcome space methods clearly outperform thedecision-space methods, even if they do not run in output-polynomial time. The compactformulation of the ILP for the $\varepsilon$-method shows a significant time improvement compared tothe conventional ILP. The new ILP formulation for the $\varepsilon$-method demonstrates significant time improvements over the conventional ILP formulation In summary, this thesis significantly contributes to the study of MOCO and especially MOIMCF by advancing algorithmic methodologies, refining theoretical foundations, and offering insights into computational complexity. By addressing gaps in the literature and proposing novel approaches, it lays the groundwork for further advancements in MOIMCF research.

Detailsuche

Bibliotheken

Projekt

Impressum

Datenschutz

Titelaufnahme