{"id":{"repo_id":"tu-berlin","oai_identifier":"oai:depositonce.tu-berlin.de:11303/26169"},"canonical_url":"https://search.dev.ndltd.org/etd/tu-berlin/oai:depositonce.tu-berlin.de:11303/26169","repository":{"repo_id":"tu-berlin","name":"Technische Universität Berlin","base_url":"https://api-depositonce.tu-berlin.de/server/oai/request"},"display":{"title":"Machine learning and combinatorial methods for discrete optimization problems","abstract":"Combinatorial optimization is a central field of discrete mathematics, concerned with finding optimal solutions to problems over combinatorial structures such as graphs or set systems. However, while classical combinatorial optimization assumes complete knowledge of all problem parameters, real-world applications often include uncertainty. Among the most important problems in this field are parallel machine scheduling problems and network flow problems, which have attracted sustained research in operations research and computer science for over half a century. In this thesis, we develop and implement algorithms for variants of these two important classes of problems. Scheduling problems, with their elegant and often minimalistic formulations make them ideal test environment for algorithm development, while they remain highly relevant to real-world domains such as manufacturing, communications, and healthcare. In most practical settings, uncertainty is the rule rather than the exception. With the rise of the digital era, stochastic information can often be inferred from the abundance of available data. This motivates the study of stochastic scheduling on parallel machines in the first part of this thesis. First, we consider one of the most important real-world applications: elective surgery planning in hospitals with shared operating rooms for both elective and emergency patients. The problem is divided into two phases: offline and online. In the offline phase, elective patients are selected, assigned to operating blocks, and given tentative start times. The online phase includes inserting emergency surgeries as they arrive and may postpone or cancel elective ones. The objective is to minimize expected total costs related to patient assignment, waiting times, surgery cancellations, and resource overtime and idle time. We model the offline phase as a two-stage stochastic program and approximate second-stage costs using a convex piecewise linear surrogate model. This results in a mixed-integer program which can be solved very quickly even for large instances. For the online phase, we propose a greedy policy. Simulations show that our approach can reduce expected costs by up to 30% compared to heuristic methods. In recent years, there has been growing interest from both the research community and industry in applying machine learning to scheduling problems. Motivated by this trend, we next apply a machine learning method to the stochastic scheduling problem in an unrelated parallel machine environment. The overall goal is to find a scheduling policy that minimizes the expected value of a cost function combining three classic objectives: weighted job tardiness, weighted machine tardiness, and makespan. We use supervised learning to train a neural network on instances solved to optimality via dynamic programming. Different representations of the stochastic information are explored during the training. The results show that the neural network policy outperforms state-of-the-art heuristics, achieving expected costs within about 1% of the true optimal policy. Additionally, the learned policy generalizes well to instances with different job duration distributions and larger problem sizes. Networks are an integral part of modern life, forming the backbone of the countless systems on which we rely daily. Network flow models cover a wide range of real-world applications; however, in many cases, splitting a commodity across multiple paths can often degrade service quality, increase operational complexity, or even be impractical. This gives rise to the need to study the unsplittable flow problem. The second part of this thesis will focus on unsplittable flow problems in digraphs. We begin with the integer and unsplittable multiflow problem in series-parallel digraphs. An unsplittable multiflow routes the demand for each commodity along a single path from its source to its sink node. As one of our main results, we prove that any multiflow in a series-parallel digraph can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. For the special case of series-parallel digraphs, this confirms a long-standing conjecture by Goemans and a stronger one by Skutella, even for general multiflows where commodities have different source and sink nodes. We also show strong integrality results for multiflows on series-parallel digraphs, showing their computation can be reduced to a simple single-commodity flow problem. We next study a variant of the unsplittable multiflow problem, namely the single-source unsplittable flow problem in general digraphs, where the demand of each commodity must be routed along a single path from a common source node to its respective sink node. We present an alternative algorithm to the one introduced by Goemans, based on the concept of residual networks. This algorithm also serves as the foundation for a heuristic method aimed at solving a more challenging variant of the problem, recently proposed by Skutella, which requires simultaneously satisfying both upper and lower bounds on arc flow values. We evaluate the heuristic on various sets of randomly generated instances. The results show that our method performs well across all sets, successfully solving most instances.","abstract_html":"Combinatorial optimization is a central field of discrete mathematics, concerned with finding optimal solutions to problems over combinatorial structures such as graphs or set systems. However, while classical combinatorial optimization assumes complete knowledge of all problem parameters, real-world applications often include uncertainty. Among the most important problems in this field are parallel machine scheduling problems and network flow problems, which have attracted sustained research in operations research and computer science for over half a century. In this thesis, we develop and implement algorithms for variants of these two important classes of problems. Scheduling problems, with their elegant and often minimalistic formulations make them ideal test environment for algorithm development, while they remain highly relevant to real-world domains such as manufacturing, communications, and healthcare. In most practical settings, uncertainty is the rule rather than the exception. With the rise of the digital era, stochastic information can often be inferred from the abundance of available data. This motivates the study of stochastic scheduling on parallel machines in the first part of this thesis. First, we consider one of the most important real-world applications: elective surgery planning in hospitals with shared operating rooms for both elective and emergency patients. The problem is divided into two phases: offline and online. In the offline phase, elective patients are selected, assigned to operating blocks, and given tentative start times. The online phase includes inserting emergency surgeries as they arrive and may postpone or cancel elective ones. The objective is to minimize expected total costs related to patient assignment, waiting times, surgery cancellations, and resource overtime and idle time. We model the offline phase as a two-stage stochastic program and approximate second-stage costs using a convex piecewise linear surrogate model. This results in a mixed-integer program which can be solved very quickly even for large instances. For the online phase, we propose a greedy policy. Simulations show that our approach can reduce expected costs by up to 30% compared to heuristic methods. In recent years, there has been growing interest from both the research community and industry in applying machine learning to scheduling problems. Motivated by this trend, we next apply a machine learning method to the stochastic scheduling problem in an unrelated parallel machine environment. The overall goal is to find a scheduling policy that minimizes the expected value of a cost function combining three classic objectives: weighted job tardiness, weighted machine tardiness, and makespan. We use supervised learning to train a neural network on instances solved to optimality via dynamic programming. Different representations of the stochastic information are explored during the training. The results show that the neural network policy outperforms state-of-the-art heuristics, achieving expected costs within about 1% of the true optimal policy. Additionally, the learned policy generalizes well to instances with different job duration distributions and larger problem sizes. Networks are an integral part of modern life, forming the backbone of the countless systems on which we rely daily. Network flow models cover a wide range of real-world applications; however, in many cases, splitting a commodity across multiple paths can often degrade service quality, increase operational complexity, or even be impractical. This gives rise to the need to study the unsplittable flow problem. The second part of this thesis will focus on unsplittable flow problems in digraphs. We begin with the integer and unsplittable multiflow problem in series-parallel digraphs. An unsplittable multiflow routes the demand for each commodity along a single path from its source to its sink node. As one of our main results, we prove that any multiflow in a series-parallel digraph can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. For the special case of series-parallel digraphs, this confirms a long-standing conjecture by Goemans and a stronger one by Skutella, even for general multiflows where commodities have different source and sink nodes. We also show strong integrality results for multiflows on series-parallel digraphs, showing their computation can be reduced to a simple single-commodity flow problem. We next study a variant of the unsplittable multiflow problem, namely the single-source unsplittable flow problem in general digraphs, where the demand of each commodity must be routed along a single path from a common source node to its respective sink node. We present an alternative algorithm to the one introduced by Goemans, based on the concept of residual networks. This algorithm also serves as the foundation for a heuristic method aimed at solving a more challenging variant of the problem, recently proposed by Skutella, which requires simultaneously satisfying both upper and lower bounds on arc flow values. We evaluate the heuristic on various sets of randomly generated instances. The results show that our method performs well across all sets, successfully solving most instances.","abstract_has_math":false,"creators":["Majthoub Almoghrabi, Mohammed"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Skutella, Martin"],"committee_chairs":[],"committee_members":[],"year":2026,"date_issued":"2026","date_published":"2026","updated_at":"2026-07-27T21:28:47Z","subjects":[],"languages":["en"],"rights":[],"rights_urls":["https://creativecommons.org/licenses/by-nc/4.0/"],"identifier_entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://doi.org/10.14279/depositonce-24997"],"render_values":[{"text":"https://doi.org/10.14279/depositonce-24997","href":"https://doi.org/10.14279/depositonce-24997","code":true}]}]},"links":{"outbound_url":"https://depositonce.tu-berlin.de/handle/11303/26169","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Skutella, Martin"]},{"key":"dc:creator","label":"Author","values":["Majthoub Almoghrabi, Mohammed"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2026-03-24T10:52:12Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2026-03-24T10:52:12Z"]},{"key":"dc:date.issued","label":"Date","values":["2026"]},{"key":"dc:type","label":"Dc Type","values":["Doctoral Thesis"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights.uri","label":"Rights URI","values":["https://creativecommons.org/licenses/by-nc/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://depositonce.tu-berlin.de/handle/11303/26169","https://doi.org/10.14279/depositonce-24997"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Combinatorial optimization is a central field of discrete mathematics, concerned with finding optimal solutions to problems over combinatorial structures such as graphs or set systems. However, while classical combinatorial optimization assumes complete knowledge of all problem parameters, real-world applications often include uncertainty. Among the most important problems in this field are parallel machine scheduling problems and network flow problems, which have attracted sustained research in operations research and computer science for over half a century. In this thesis, we develop and implement algorithms for variants of these two important classes of problems. Scheduling problems, with their elegant and often minimalistic formulations make them ideal test environment for algorithm development, while they remain highly relevant to real-world domains such as manufacturing, communications, and healthcare. In most practical settings, uncertainty is the rule rather than the exception. With the rise of the digital era, stochastic information can often be inferred from the abundance of available data. This motivates the study of stochastic scheduling on parallel machines in the first part of this thesis. First, we consider one of the most important real-world applications: elective surgery planning in hospitals with shared operating rooms for both elective and emergency patients. The problem is divided into two phases: offline and online. In the offline phase, elective patients are selected, assigned to operating blocks, and given tentative start times. The online phase includes inserting emergency surgeries as they arrive and may postpone or cancel elective ones. The objective is to minimize expected total costs related to patient assignment, waiting times, surgery cancellations, and resource overtime and idle time. We model the offline phase as a two-stage stochastic program and approximate second-stage costs using a convex piecewise linear surrogate model. This results in a mixed-integer program which can be solved very quickly even for large instances. For the online phase, we propose a greedy policy. Simulations show that our approach can reduce expected costs by up to 30% compared to heuristic methods. In recent years, there has been growing interest from both the research community and industry in applying machine learning to scheduling problems. Motivated by this trend, we next apply a machine learning method to the stochastic scheduling problem in an unrelated parallel machine environment. The overall goal is to find a scheduling policy that minimizes the expected value of a cost function combining three classic objectives: weighted job tardiness, weighted machine tardiness, and makespan. We use supervised learning to train a neural network on instances solved to optimality via dynamic programming. Different representations of the stochastic information are explored during the training. The results show that the neural network policy outperforms state-of-the-art heuristics, achieving expected costs within about 1% of the true optimal policy. Additionally, the learned policy generalizes well to instances with different job duration distributions and larger problem sizes. Networks are an integral part of modern life, forming the backbone of the countless systems on which we rely daily. Network flow models cover a wide range of real-world applications; however, in many cases, splitting a commodity across multiple paths can often degrade service quality, increase operational complexity, or even be impractical. This gives rise to the need to study the unsplittable flow problem. The second part of this thesis will focus on unsplittable flow problems in digraphs. We begin with the integer and unsplittable multiflow problem in series-parallel digraphs. An unsplittable multiflow routes the demand for each commodity along a single path from its source to its sink node. As one of our main results, we prove that any multiflow in a series-parallel digraph can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. For the special case of series-parallel digraphs, this confirms a long-standing conjecture by Goemans and a stronger one by Skutella, even for general multiflows where commodities have different source and sink nodes. We also show strong integrality results for multiflows on series-parallel digraphs, showing their computation can be reduced to a simple single-commodity flow problem. We next study a variant of the unsplittable multiflow problem, namely the single-source unsplittable flow problem in general digraphs, where the demand of each commodity must be routed along a single path from a common source node to its respective sink node. We present an alternative algorithm to the one introduced by Goemans, based on the concept of residual networks. This algorithm also serves as the foundation for a heuristic method aimed at solving a more challenging variant of the problem, recently proposed by Skutella, which requires simultaneously satisfying both upper and lower bounds on arc flow values. We evaluate the heuristic on various sets of randomly generated instances. The results show that our method performs well across all sets, successfully solving most instances.","Kombinatorische Optimierung ist ein zentrales Teilgebiet der diskreten Mathematik, das sich mit der Suche nach optimalen Lösungen über kombinatorischen Strukturen wie Graphen oder Mengensystemen befasst. Während in der klassischen kombinatorischen Optimierung vollständige Informationen über alle Problemparameter vorausgesetzt werden, ist in realen Anwendungen Unsicherheit häufig unvermeidbar. Zu den wichtigsten Problemklassen in diesem Bereich zählen Planungsprobleme auf parallelen Maschinen sowie Netzwerkflussprobleme, die seit über einem halben Jahrhundert im Fokus der Forschung in den Bereichen Operations Research und Informatik stehen. In dieser Arbeit entwickeln und implementieren wir Algorithmen für Varianten dieser beiden bedeutenden Klassen kombinatorischer Optimierungsprobleme. Planungsprobleme zeichnen sich durch elegante und oftmals minimalistische Modellierungen aus, was sie zu idealen Testumgebungen für die Entwicklung neuer Algorithmen macht. Gleichzeitig besitzen sie eine hohe praktische Relevanz in zahlreichen Anwendungsbereichen wie der Fertigungsindustrie, der Telekommunikation und dem Gesundheitswesen. In den meisten realen Szenarien ist Unsicherheit eher die Regel als die Ausnahme. Mit dem Aufkommen des digitalen Zeitalters lässt sich stochastische Information zunehmend aus der Fülle verfügbarer Daten gewinnen. Dies motiviert die Auseinandersetzung mit stochastischen Planungsproblemen im ersten Teil dieser Dissertation. Zunächst betrachten wir eine der wichtigsten realweltlichen Anwendungen: die Operationsplanung in Krankenhäusern mit gemeinsam genutzten Operationssälen für elektive und Notfallpatienten. Das Problem wird in zwei Phasen unterteilt: eine Offline- und eine Online-Phase. In der Offline-Phase werden elektive Patienten ausgewählt, Operationsblöcken zugewiesen und mit vorläufigen Startzeiten versehen. In der Online-Phase werden eintreffende Notfalloperationen eingefügt, und gegebenenfalls werden elektive Eingriffe verschoben oder abgesagt. Das Ziel besteht darin, die erwarteten Gesamtkosten zu minimieren, die sich aus der Patientenverteilung, den Wartezeiten, OP-Absagen sowie den Überstunden und Leerlaufzeiten der Ressourcen ergeben. Die Offline-Phase wird als zweistufiges stochastisches Programm modelliert, und die Kosten der zweiten Stufe werden mithilfe eines stückweise linearen, konvexen Surrogatmodells approximiert. Dadurch ergibt sich ein gemischt-ganzzahliges Optimierungsproblem, das selbst für große Instanzen sehr effizient lösbar ist. Für die Online-Phase schlagen wir eine “greedy” Entscheidungsregel vor. Simulationen zeigen, dass unser Ansatz die erwarteten Kosten im Vergleich zu heuristischen Verfahren um bis zu 30% senken kann. In den vergangenen Jahren ist sowohl in der Forschung als auch in der Industrie das Interesse an der Anwendung von Methoden des maschinellen Lernens auf Planungsprobleme stark gewachsen. Vor diesem Hintergrund wenden wir Methoden des maschinellen Lernens auf das stochastische Planungsproblem für unabhängige parallele Maschinen an. Ziel ist es, eine Policy zu ermitteln, die den Erwartungswert einer Kostenfunktion minimiert, welche drei klassische Zielgrößen kombiniert: gewichtete Verspätung der Aufträge (weighted job tardiness), gewichtete Maschinenverspätung (weighted machine tardiness) und die Gesamtdauer (makespan). Hierfür nutzen wir überwachtes Lernen (supervised learning), um ein neuronales Netzwerk auf Instanzen zu trainieren, die mittels dynamischer Programmierung optimal gelöst wurden. Dabei werden verschiedene Repräsentationen der stochastischen Informationen während des Trainingsprozesses untersucht. Die Ergebnisse zeigen, dass die durch das neuronale Netzwerk gelernte Policy gegenüber etablierten heuristischen Verfahren überlegen ist und erwartete Kosten erzielt, die nur etwa 1% über denen der optimalen Policy liegen. Darüber hinaus generalisiert die gelernte Policy gut auf Instanzen mit anderen Verteilungen der Auftragsdauern sowie auf größere Problemgrößen. Netzwerke sind ein integraler Bestandteil des modernen Lebens und bilden das Rückgrat unzähliger Systeme, auf die wir täglich angewiesen sind. Netzwerkflussmodelle decken ein breites Spektrum realweltlicher Anwendungen ab. In vielen Fällen kann das Aufteilen des Flusses auf mehrere Pfade jedoch die Dienstleistungsqualität beeinträchtigen, die operative Komplexität erhöhen oder sich als praktisch undurchführbar erweisen. Daraus ergibt sich die Notwendigkeit, das sogenannte Unteilbarer-Fluss-Problem zu untersuchen. Der zweite Teil dieser Dissertation widmet sich daher dem Unteilbarer-Fluss-Problem in gerichteten Graphen. Wir beginnen mit dem ganzzahligen Unteilbarer-Multifluss-Problem in serien-parallelen Digraphen (series-parallel digraphs). Ein unteilbarer Multifluss routet die Nachfrage jeder Ware entlang eines einzigen Pfades vom Start- zum Zielknoten. Als eines unserer zentralen Ergebnisse zeigen wir, dass sich jeder Multifluss in einem serien-parallelen Digraphen als konvexe Kombination von unteilbaren Multifluss-Lösungen darstellen lässt, wobei der Fluss auf jeder Kante höchstens um die maximale Nachfrage einer Ware vom ursprünglichen Fluss abweicht. Für den Spezialfall serien-paralleler Digraphen bestätigt dies eine langjährige Vermutung von Goemans sowie eine stärkere Version dieser Vermutung von Skutella – und zwar auch für allgemeine Multifluss-Probleme, bei denen die Waren unterschiedliche Start- und Zielknoten besitzen. Darüber hinaus zeigen wir starke Ganzzahligkeitseigenschaften für Multifluss-Probleme auf serien-parallelen Digraphen und beweisen, dass sich ihre Berechnung auf ein einfaches Einzelwarenfluss-Problem (single-commodity flow) reduzieren lässt. Anschließend untersuchen wir eine Variante des Unteilbarer-Multifluss-Problems, das sogenannte Single Source Unteilbarer-Fluss-Problem, in allgemeinen Digraphen. Dabei muss die Nachfrage jeder Ware entlang eines einzigen Pfads von einem gemeinsamen Startknoten zu einem jeweils spezifischen Zielknoten geleitet werden. Wir präsentieren einen alternativen Algorithmus zu dem von Goemans vorgeschlagenen Verfahren, der auf dem Konzept Residualnetzwerk (residual networks) basiert. Dieser Algorithmus bildet zugleich die Grundlage für eine heuristische Methode zur Lösung einer kürzlich von Skutella vorgeschlagenen anspruchsvolleren Problemvariante. Diese erfordert, dass sowohl obere als auch untere Schranken auf den Kantenflüssen gleichzeitig eingehalten werden. Wir evaluieren die Heuristik auf verschiedenen Mengen zufällig generierter Instanzen. Die Ergebnisse zeigen, dass unsere Methode über alle Instanzenmengen hinweg gut funktioniert und die meisten Instanzen erfolgreich löst."]},{"key":"dc:title","label":"Title","values":["Machine learning and combinatorial methods for discrete optimization problems"]}]}],"canonical_facts":{"dc:contributor.advisor":["Skutella, Martin"],"dc:creator":["Majthoub Almoghrabi, Mohammed"],"dc:date.accessioned":["2026-03-24T10:52:12Z"],"dc:date.available":["2026-03-24T10:52:12Z"],"dc:date.issued":["2026"],"dc:description.abstract":["Combinatorial optimization is a central field of discrete mathematics, concerned with finding optimal solutions to problems over combinatorial structures such as graphs or set systems. However, while classical combinatorial optimization assumes complete knowledge of all problem parameters, real-world applications often include uncertainty. Among the most important problems in this field are parallel machine scheduling problems and network flow problems, which have attracted sustained research in operations research and computer science for over half a century. In this thesis, we develop and implement algorithms for variants of these two important classes of problems. Scheduling problems, with their elegant and often minimalistic formulations make them ideal test environment for algorithm development, while they remain highly relevant to real-world domains such as manufacturing, communications, and healthcare. In most practical settings, uncertainty is the rule rather than the exception. With the rise of the digital era, stochastic information can often be inferred from the abundance of available data. This motivates the study of stochastic scheduling on parallel machines in the first part of this thesis. First, we consider one of the most important real-world applications: elective surgery planning in hospitals with shared operating rooms for both elective and emergency patients. The problem is divided into two phases: offline and online. In the offline phase, elective patients are selected, assigned to operating blocks, and given tentative start times. The online phase includes inserting emergency surgeries as they arrive and may postpone or cancel elective ones. The objective is to minimize expected total costs related to patient assignment, waiting times, surgery cancellations, and resource overtime and idle time. We model the offline phase as a two-stage stochastic program and approximate second-stage costs using a convex piecewise linear surrogate model. This results in a mixed-integer program which can be solved very quickly even for large instances. For the online phase, we propose a greedy policy. Simulations show that our approach can reduce expected costs by up to 30% compared to heuristic methods. In recent years, there has been growing interest from both the research community and industry in applying machine learning to scheduling problems. Motivated by this trend, we next apply a machine learning method to the stochastic scheduling problem in an unrelated parallel machine environment. The overall goal is to find a scheduling policy that minimizes the expected value of a cost function combining three classic objectives: weighted job tardiness, weighted machine tardiness, and makespan. We use supervised learning to train a neural network on instances solved to optimality via dynamic programming. Different representations of the stochastic information are explored during the training. The results show that the neural network policy outperforms state-of-the-art heuristics, achieving expected costs within about 1% of the true optimal policy. Additionally, the learned policy generalizes well to instances with different job duration distributions and larger problem sizes. Networks are an integral part of modern life, forming the backbone of the countless systems on which we rely daily. Network flow models cover a wide range of real-world applications; however, in many cases, splitting a commodity across multiple paths can often degrade service quality, increase operational complexity, or even be impractical. This gives rise to the need to study the unsplittable flow problem. The second part of this thesis will focus on unsplittable flow problems in digraphs. We begin with the integer and unsplittable multiflow problem in series-parallel digraphs. An unsplittable multiflow routes the demand for each commodity along a single path from its source to its sink node. As one of our main results, we prove that any multiflow in a series-parallel digraph can be expressed as a convex combination of unsplittable multiflows, where the total flow on any arc deviates from the given flow by less than the maximum demand of any commodity. For the special case of series-parallel digraphs, this confirms a long-standing conjecture by Goemans and a stronger one by Skutella, even for general multiflows where commodities have different source and sink nodes. We also show strong integrality results for multiflows on series-parallel digraphs, showing their computation can be reduced to a simple single-commodity flow problem. We next study a variant of the unsplittable multiflow problem, namely the single-source unsplittable flow problem in general digraphs, where the demand of each commodity must be routed along a single path from a common source node to its respective sink node. We present an alternative algorithm to the one introduced by Goemans, based on the concept of residual networks. This algorithm also serves as the foundation for a heuristic method aimed at solving a more challenging variant of the problem, recently proposed by Skutella, which requires simultaneously satisfying both upper and lower bounds on arc flow values. We evaluate the heuristic on various sets of randomly generated instances. The results show that our method performs well across all sets, successfully solving most instances.","Kombinatorische Optimierung ist ein zentrales Teilgebiet der diskreten Mathematik, das sich mit der Suche nach optimalen Lösungen über kombinatorischen Strukturen wie Graphen oder Mengensystemen befasst. Während in der klassischen kombinatorischen Optimierung vollständige Informationen über alle Problemparameter vorausgesetzt werden, ist in realen Anwendungen Unsicherheit häufig unvermeidbar. Zu den wichtigsten Problemklassen in diesem Bereich zählen Planungsprobleme auf parallelen Maschinen sowie Netzwerkflussprobleme, die seit über einem halben Jahrhundert im Fokus der Forschung in den Bereichen Operations Research und Informatik stehen. In dieser Arbeit entwickeln und implementieren wir Algorithmen für Varianten dieser beiden bedeutenden Klassen kombinatorischer Optimierungsprobleme. Planungsprobleme zeichnen sich durch elegante und oftmals minimalistische Modellierungen aus, was sie zu idealen Testumgebungen für die Entwicklung neuer Algorithmen macht. Gleichzeitig besitzen sie eine hohe praktische Relevanz in zahlreichen Anwendungsbereichen wie der Fertigungsindustrie, der Telekommunikation und dem Gesundheitswesen. In den meisten realen Szenarien ist Unsicherheit eher die Regel als die Ausnahme. Mit dem Aufkommen des digitalen Zeitalters lässt sich stochastische Information zunehmend aus der Fülle verfügbarer Daten gewinnen. Dies motiviert die Auseinandersetzung mit stochastischen Planungsproblemen im ersten Teil dieser Dissertation. Zunächst betrachten wir eine der wichtigsten realweltlichen Anwendungen: die Operationsplanung in Krankenhäusern mit gemeinsam genutzten Operationssälen für elektive und Notfallpatienten. Das Problem wird in zwei Phasen unterteilt: eine Offline- und eine Online-Phase. In der Offline-Phase werden elektive Patienten ausgewählt, Operationsblöcken zugewiesen und mit vorläufigen Startzeiten versehen. In der Online-Phase werden eintreffende Notfalloperationen eingefügt, und gegebenenfalls werden elektive Eingriffe verschoben oder abgesagt. Das Ziel besteht darin, die erwarteten Gesamtkosten zu minimieren, die sich aus der Patientenverteilung, den Wartezeiten, OP-Absagen sowie den Überstunden und Leerlaufzeiten der Ressourcen ergeben. Die Offline-Phase wird als zweistufiges stochastisches Programm modelliert, und die Kosten der zweiten Stufe werden mithilfe eines stückweise linearen, konvexen Surrogatmodells approximiert. Dadurch ergibt sich ein gemischt-ganzzahliges Optimierungsproblem, das selbst für große Instanzen sehr effizient lösbar ist. Für die Online-Phase schlagen wir eine “greedy” Entscheidungsregel vor. Simulationen zeigen, dass unser Ansatz die erwarteten Kosten im Vergleich zu heuristischen Verfahren um bis zu 30% senken kann. In den vergangenen Jahren ist sowohl in der Forschung als auch in der Industrie das Interesse an der Anwendung von Methoden des maschinellen Lernens auf Planungsprobleme stark gewachsen. Vor diesem Hintergrund wenden wir Methoden des maschinellen Lernens auf das stochastische Planungsproblem für unabhängige parallele Maschinen an. Ziel ist es, eine Policy zu ermitteln, die den Erwartungswert einer Kostenfunktion minimiert, welche drei klassische Zielgrößen kombiniert: gewichtete Verspätung der Aufträge (weighted job tardiness), gewichtete Maschinenverspätung (weighted machine tardiness) und die Gesamtdauer (makespan). Hierfür nutzen wir überwachtes Lernen (supervised learning), um ein neuronales Netzwerk auf Instanzen zu trainieren, die mittels dynamischer Programmierung optimal gelöst wurden. Dabei werden verschiedene Repräsentationen der stochastischen Informationen während des Trainingsprozesses untersucht. Die Ergebnisse zeigen, dass die durch das neuronale Netzwerk gelernte Policy gegenüber etablierten heuristischen Verfahren überlegen ist und erwartete Kosten erzielt, die nur etwa 1% über denen der optimalen Policy liegen. Darüber hinaus generalisiert die gelernte Policy gut auf Instanzen mit anderen Verteilungen der Auftragsdauern sowie auf größere Problemgrößen. Netzwerke sind ein integraler Bestandteil des modernen Lebens und bilden das Rückgrat unzähliger Systeme, auf die wir täglich angewiesen sind. Netzwerkflussmodelle decken ein breites Spektrum realweltlicher Anwendungen ab. In vielen Fällen kann das Aufteilen des Flusses auf mehrere Pfade jedoch die Dienstleistungsqualität beeinträchtigen, die operative Komplexität erhöhen oder sich als praktisch undurchführbar erweisen. Daraus ergibt sich die Notwendigkeit, das sogenannte Unteilbarer-Fluss-Problem zu untersuchen. Der zweite Teil dieser Dissertation widmet sich daher dem Unteilbarer-Fluss-Problem in gerichteten Graphen. Wir beginnen mit dem ganzzahligen Unteilbarer-Multifluss-Problem in serien-parallelen Digraphen (series-parallel digraphs). Ein unteilbarer Multifluss routet die Nachfrage jeder Ware entlang eines einzigen Pfades vom Start- zum Zielknoten. Als eines unserer zentralen Ergebnisse zeigen wir, dass sich jeder Multifluss in einem serien-parallelen Digraphen als konvexe Kombination von unteilbaren Multifluss-Lösungen darstellen lässt, wobei der Fluss auf jeder Kante höchstens um die maximale Nachfrage einer Ware vom ursprünglichen Fluss abweicht. Für den Spezialfall serien-paralleler Digraphen bestätigt dies eine langjährige Vermutung von Goemans sowie eine stärkere Version dieser Vermutung von Skutella – und zwar auch für allgemeine Multifluss-Probleme, bei denen die Waren unterschiedliche Start- und Zielknoten besitzen. Darüber hinaus zeigen wir starke Ganzzahligkeitseigenschaften für Multifluss-Probleme auf serien-parallelen Digraphen und beweisen, dass sich ihre Berechnung auf ein einfaches Einzelwarenfluss-Problem (single-commodity flow) reduzieren lässt. Anschließend untersuchen wir eine Variante des Unteilbarer-Multifluss-Problems, das sogenannte Single Source Unteilbarer-Fluss-Problem, in allgemeinen Digraphen. Dabei muss die Nachfrage jeder Ware entlang eines einzigen Pfads von einem gemeinsamen Startknoten zu einem jeweils spezifischen Zielknoten geleitet werden. Wir präsentieren einen alternativen Algorithmus zu dem von Goemans vorgeschlagenen Verfahren, der auf dem Konzept Residualnetzwerk (residual networks) basiert. Dieser Algorithmus bildet zugleich die Grundlage für eine heuristische Methode zur Lösung einer kürzlich von Skutella vorgeschlagenen anspruchsvolleren Problemvariante. Diese erfordert, dass sowohl obere als auch untere Schranken auf den Kantenflüssen gleichzeitig eingehalten werden. Wir evaluieren die Heuristik auf verschiedenen Mengen zufällig generierter Instanzen. Die Ergebnisse zeigen, dass unsere Methode über alle Instanzenmengen hinweg gut funktioniert und die meisten Instanzen erfolgreich löst."],"dc:identifier.uri":["https://depositonce.tu-berlin.de/handle/11303/26169","https://doi.org/10.14279/depositonce-24997"],"dc:language.iso":["en"],"dc:rights.uri":["https://creativecommons.org/licenses/by-nc/4.0/"],"dc:title":["Machine learning and combinatorial methods for discrete optimization problems"],"dc:type":["Doctoral Thesis"]},"updated_at":"2026-07-27T21:28:47Z"}