TY - RPRT A1 - Gnegel, Fabian A1 - Fügenschuh, Armin A1 - Hagel, Michael A1 - Leyffer, Sven A1 - Stiemer, Marcus ED - Fügenschuh, Armin T1 - A solution framework for linear PDE-constrained mixed-integer problems N2 - We present a general numerical solution method for control problems with PDE-defined state variables over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs (and if necessary a linearization scheme) to derive constraints for a mixed-integer linear program (MILP) leads to systems that are too large to be solved with state-of-the-art solvers for MILPs, especially if we desire an accurate approximation of the state variables. Our framework comprises two techniques to mitigate the rise of computation times with increasing discretization level parameters: First, the linear system is solved for a basis of the control space in a preprocessing step. Second, certain constraints are just imposed on demand via the IBM ILOG CPLEX feature of a lazy constraint callback. These techniques are compared with an approach where the relations obtained by the discretization of the continuous constraints are directly included in the MILP. We demonstrate our approach on two examples: modeling of the spread of wildfire and the mitigation of water contamination. In both examples the computational results demonstrate that the solution time is significantly reduced by our methods. In particular, the dependence of the computation time on the size of the spatial discretization of the PDE is significantly reduced. N2 - Wir präsentieren eine allgemeine numerische Lösungsmethode für Steuerungsprobleme mit PDE-definierten Zustandsvariablen über einer endlichen Menge von binären oder kontinuierlichen Steuerungsvariablen. Wir zeigen empirisch, dass ein naiver Ansatz, der ein numerisches Diskretisierungsschema auf die PDEs anwendet (und erforderlichenfalls ein Linearisierungsschema), um Nebenbedingungen für ein gemischt-ganzzahliges lineares Programm (MILP) abzuleiten, zu Systemen führt, die zu groß sind, um selbst mit modernen MILP-Lösern gelöst zu werden, insbesondere wenn eine genaue Approximation der Zustandsvariablen gewünscht ist. Unser Ansatz umfasst zwei Techniken, um den Anstieg der Rechenzeiten mit zunehmender Feinheit der Diskretisierung abzumildern: Erstens wird das lineare System in einem Vorverarbeitungsschritt in den Variablen des Kontrollraums gelöst. Zweitens werden bestimmte Einschränkungen nur bei Bedarf über die IBM ILOG CPLEX-Funktion einer verzögerten Nebenbedingungs-Generierung zur Instanz hinzugefügt. Diese Techniken werden mit einem Ansatz verglichen, bei dem die durch die Diskretisierung der kontinuierlichen Nebenbedingungen erhaltenen Beziehungen direkt in das MILP einbezogen werden. Wir zeigen unseren Ansatz an zwei Beispielen: Modellierung der Ausbreitung eines Waldbrands und Minderung einer Wasserverschmutzung. In beiden Beispielen zeigen die Berechnungsergebnisse, dass die Lösungszeit durch unsere Methoden erheblich verkürzt wird. Insbesondere wird die Abhängigkeit der Rechenzeit von der Größe der räumlichen Diskretisierung der PDE deutlich reduziert. T3 - Cottbus Mathematical Preprints - 8,2019 KW - Mixed-integer linear programming KW - Partial differential equations KW - Finite-element methods KW - Convection-diffusion equation KW - Global optimal control KW - Gemischt-ganzzahlige lineare Programmierung KW - Globale Optimalsteuerung KW - Konvektions-Diffusions-Gleichung KW - Finite-Elemente-Methode KW - Partielle Differentialgleichungen KW - Optimale Kontrolle KW - Finite-Elemente-Methode KW - Lineare Optimierung KW - Konvektions-Diffusionsgleichung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50453 SN - 2627-6100 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Schaudt, Stefan A1 - Clausen, Uwe A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A 2D layered graph approach for scheduling delivery robots T1 - Ein geschichteter 2D Graphen Ansatz für die Ablaufplanung von Lieferrobotern N2 - In recent years parcel volumes reached record highs. The logistics industry is seeking new innovative concepts to keep pace. For densely populated areas delivery robots are a promising alternative to conventional trucking. These electric robots drive autonomously on sidewalks and deliver urgent goods, such as express parcels, medicine, or meals. The limited cargo space and battery capacity of these vehicles necessitates a depot visit after each customer served. The problem can be formulated as an electric vehicle routing problem with soft time windows and a single unit capacity. The goal is to serve all customers such that the quadratic sum of delays is minimized and each vehicle operates within its battery bounds. To solve this problem, we formulate an MIQP and present an expanded formulation based on a layered graph. For this layered graph we derive two solution approaches based on relaxations, which use less nodes and arcs. The first, Iterative Refinement, always solves the current relaxation to optimality and refines the graph if the solution is not feasible for the expanded formulation. This is repeated until a proven optimal solution is found. The second, Branch and Refine, integrates the graph refinement into a branch and bound framework avoiding restarts. Computational experiments performed on modified Solomon instances demonstrate the advantage of using our solution approaches and show that Branch and Refine outperforms Iterative Refinement in all studied parameter configurations. N2 - In den letzten Jahren erreichte das Paketvolumen Rekordhöhen. Die Logistikbranche sucht nach neuen innovativen Konzepten, um Schritt zu halten. Für dicht besiedelte Gebiete sind Lieferroboter eine vielversprechende Alternative zum konventionellen LKW-Transport. Diese elektrischen Roboter fahren autonom auf Bürgersteigen und liefern Waren wie Expresspakete, Medikamente oder Mahlzeiten aus. Der begrenzte Laderaum und die begrenzte Batteriekapazität dieser Fahrzeuge erfordern nach jedem Kunden einen Depotbesuch. Das Problem kann als Routingproblem für Elektrofahrzeuge mit weichen Zeitfenstern und einer Kapazität von einer einzelnen Einheit formuliert werden. Ziel ist es, alle Kunden so zu bedienen, dass die quadratische Summe der Verspätungen minimiert wird und jede Fahrzeugroute innerhalb der Batterieladungsgrenzen liegt. Um dieses Problem zu lösen, formulieren wir einen MIQP und präsentieren eine erweiterte Formulierung basierend auf einem geschichteten Graphen. Für diesen geschichtete Graphen leiten wir zwei Lösungsansätze ab, die auf Relaxationen basieren und weniger Knoten und Bögen verwenden. Der erste, iterative Verfeinerung, löst die aktuelle Relaxation immer optimal und verfeinert den Graphen, wenn die erweiterte Formulierung keine zulässige Lösung enthält. Dies wird wiederholt, bis eine optimale Lösung gefunden ist. Die zweite Option, Verzweigen und Verfeinern, integriert die Graphenverfeinerung in einen Verzweige und Beschränke Rahmen, um Neustarts zu vermeiden. Computerexperimente, die an modifizierten Solomon-Instanzen durchgeführt wurden, zeigen den Vorteil der Verwendung unserer Lösungsansätze und zeigen, dass Verzweigen und Verfeinern die iterative Verfeinerung in allen untersuchten Parameterkonfigurationen übertrifft. T3 - Cottbus Mathematical Preprints - 17, 2021 KW - Delivery robots KW - Electric vehicle routing problem KW - Graph refinement KW - Layered graphs KW - Partial recharging KW - Lieferroboter KW - Streckenplanung für elektrische Fahrzeuge KW - Graphenverfeinerung KW - Geschichtete Graphen KW - Partielles Aufladen KW - Mobiler Roboter KW - Tourenplanung KW - Optimierung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54931 SN - 2627-6100 ER - TY - THES A1 - Gnegel, Fabian ED - Fügenschuh, Armin T1 - Refinement algorithms for time-dependent discrete optimization problems T1 - Verfeinerungsalgorithmen für zeitabhängige diskrete Optimierungsprobleme N2 - One of the standard approaches for solving discrete optimization problems which include the aspect of time, such as the traveling salesman problem with time windows, is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion that might contain time-infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation allows for a feasible schedule, an optimal solution can be derived from it and the algorithm terminates. In this work, we first present new ideas that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms. More precisely, we present two general algorithms for solving Mixed Integer Linear Program formulations which we call iterative refinement and branch-and-refine. Iterative refinement basically is solving relaxations of the problem until a feasible solution to the original problem is found. Branch-and-refine is a kind of branch-and-bound algorithm that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree. For demonstrating the practical relevance of these algorithms, we not only study them in the context of academic examples but also apply them to two real-world problems. The first is a problem from the literature, where small passenger air-crafts have to be routed and scheduled to serve flight requests while fulfilling a variety of conditions on, for example, fuel consumption, weight, and detours. We show here that refinement algorithms can be used to improve the best known results from the literature. The second problem we consider is the task of optimally scheduling deliveries and charging times of delivery robots such that delays are minimized. In this case, we show that refinement algorithms perform better than a direct solution approach making use of state-of-the-art solvers. N2 - Das Herleiten einer so genannten zeitindizierten Formulierung ist einer der Standardansätze zum Lösen diskreter Optimierungsprobleme, die den Aspekt der Zeit einbeziehen, wie z. B. das Problem des Handlungsreisenden mit Zeitfenstern. Liegt dem Problem eine Struktur zugrunde, die durch einen Graphen beschrieben werden kann, so basiert die zeitindizierte Formulierung in der Regel auf einem anderen, erweiterten Graphen, der gemeinhin als zeitexpandierter Graph bezeichnet wird. Der zeitexpandierte Graph kann oft so konstruiert werden, dass alle zeitlichen Beschränkungen bereits in seine Topologie einfließen und Algorithmen für die entsprechende zeitunabhängige Variante anwendbar werden. Der Nachteil dieses Ansatzes ist, dass die Mengen der Knoten und Bögen des zeitexpandierten Graphen viel größer sind als die des ursprünglichen Graphen. In neueren Arbeiten wurde jedoch gezeigt, dass für viele praktische Anwendungen eine partielle Expansion des Graphen, die möglicherweise nicht alle zeitlich unzulässigen Pfade verbietet, oft ausreicht, um eine nachweislich optimale Lösung zu finden. Bei diesem Ansatz wird stattdessen der zeitexpandierte Graph iterativ sukzessive aufgebaut und verfeinert und in jedem Schritt wird eine Relaxierung der zeitexpandierten Formulierung gelöst. Wenn die Lösung der aktuellen Relaxierung einen realisierbaren Zeitplan zulässt, kann daraus eine optimale Lösung abgeleitet werden und der Algorithmus wird beendet. In dieser Arbeit stellen wir zunächst neue Ideen vor, die es ermöglichen, Informationen über die optimale Lösung eines gröberen Graphen auf einen verfeinerten Graphen zu übertragen, und zeigen, wie diese in Algorithmen verwendet werden können. Genauer gesagt stellen wir zwei allgemeine Algorithmen zur Lösung von gemischt-ganzzahligen linearen Programmen vor, die wir als `iterative refinement' und `branch-and-refine' bezeichnen. Bei der iterativen Verfeinerung geht es im Wesentlichen darum, Relaxierungen des Problems zu lösen, bis eine machbare Lösung für das ursprüngliche Problem gefunden wird. Branch-and-refine ist eine Art Branch-and-Bound-Algorithmus, bei dem die Verfeinerung des Graphen während der Erkundung des Branch-and-Bound-Suchbaums durchgeführt wird. Um die praktische Relevanz dieser Algorithmen zu demonstrieren, untersuchen wir ihn nicht nur im Zusammenhang mit akademischen Beispielen, sondern wenden ihn auch auf zwei praktisch motivierte Fragestellungen an. Das erste ist ein Problem aus der Literatur, bei dem die Routen und Zeitpläne kleiner Passagierflugzeuge so geplant werden müssen, dass Fluganfragen von Touristengruppen zu bedienen und dabei eine Vielzahl von Bedingungen zu erfüllen. Die Bedingungen betreffen unter anderem Treibstoffverbrauch, Gewicht und Umwege. Wir zeigen hier, dass Verfeinerungsalgorithmen verwendet werden können, um die besten Ergebnisse aus der Literatur zu verbessern. Das zweite Problem, das wir betrachten, ist die Aufgabe, Lieferungen und Ladezeiten von elektrischen Lieferrobotern optimal zu planen, so dass Verzögerungen minimiert werden. In diesem Fall zeigen wir, dass Verfeinerungsalgorithmen besser abschneiden als ein direkter Lösungsansatz, bei dem ein allgemeiner Löser für gemischt-ganzzahlige Probleme eingesetzt wird. T3 - Cottbus Mathematical Preprints - 27, 2022 KW - Discrete optimization KW - Mixed integer linear programming KW - Graph refinement KW - Branch and bound KW - Time-dependent airplane routing KW - Diskrete Optimierung KW - Gemischt-ganzzahlige lineare Programmierung KW - Verfeinerung von Graphen KW - Zeitabhängige Flugroutenplanung KW - Tourenplanung von E-Fahrzeugen KW - Ganzzahlige Optimierung KW - Tourenplanung KW - Travelling-salesman-Problem KW - Branch-and-Bound-Methode Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-61275 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Branch-and-refine for solving time-dependent problems T1 - Branch-and-Refine zur Lösung zeitabhängiger Probleme N2 - Einer der Standardansätze zur Lösung zeitabhängiger diskreter Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden mit Zeitfenstern oder das Kürzeste Wege Problem mit Zeitfenstern, ist die Herleitung einer sogenannten zeitindizierten Formulierung. Wenn dem Problem eine Struktur zu Grunde liegt, die durch einen Graphen beschrieben werden kann, basiert die zeitindizierte Formulierung normalerweise auf einem anderen, erweiterten Graphen, der in der Literatur als zeitexpandierter Graph bezeichnet wird. Der zeitexpandierte Graph kann oft so generiert werden, dass alle Zeitbeschränkungen bereits aufgrund seiner Topologie erfüllt sind und somit Algorithmen für die entsprechende zeitunabhängige Variante angewendet werden können. Der Nachteil dieses Ansatzes ist, dass die Mengen der Ecken und Bögen des zeitexpandierten Graphen viel größer sind als die des ursprünglichen Graphen. In neueren Arbeiten hat sich jedoch gezeigt, dass für viele praktische Anwendungen eine partielle Expandierung des Graphen, die möglicherweise zeitunmögliche Pfade zulässt, oft ausreicht, um eine beweisbar optimale Lösung zu finden. Diese Ansätze verfeinern iterativ den ursprünglichen Graphen und lösen in jeder Iteration eine Relaxierung der zeitexpandierten Formulierung. Wenn die Lösung der aktuellen Relaxation alle Zeitbeschränkungen erfüllt, kann daraus eine optimale Lösung abgeleitet werden, und der Algorithmus terminiert. In dieser Arbeit stellen wir neue Ideen vor, die das Übertragen von Informationen über die optimale Lösung eines gröberen Graphen zu einem verfeinerten Graphen ermöglichen und zeigen, wie diese in Algorithmen verwendet werden können. Genauer gesagt stellen wir einen neuen Algorithmus zur Lösung von MILP-Formulierungen (Mixed Integer Linear Program) von zeitabhängigen Problemen vor, der es ermöglicht, die Graphenverfeinerung während der Untersuchung des Branch-and-Bound Baums durchzuführen, anstatt jedes Mal neu zu starten, wenn die optimale Lösung sich als nicht zulässig herausgestellt hat. Um die praktische Relevanz dieses Algorithmus zu demonstrieren, präsentieren wir Ergebnisse von numerische Experimenten seiner Anwendung auf das Kürzeste Wege Problem mit Zeitfenstern und das Problem des Handlungsreisenden mit Zeitfenstern. N2 - One of the standard approaches for solving time-dependent discrete optimization problems, such as the travelling salesman problem with time-windows or the shortest path problem with time-windows is to derive a so-called time-indexed formulation. If the problem has an underlying structure that can be described by a graph, the time-indexed formulation is usually based on a different, extended graph, commonly referred to as the time-expanded graph. The time-expanded graph can often be derived in such a way that all time constraints are incorporated in its topology, and therefore algorithms for the corresponding time-independent variant become applicable. The downside of this approach is, that the sets of vertices and arcs of the time-expanded graph are much larger than the ones of the original graph. In recent works, however, it has been shown that for many practical applications a partial graph expansion, that might contain time infeasible paths, often suffices to find a proven optimal solution. These approaches, instead, iteratively refine the original graph and solve a relaxation of the time-expanded formulation in each iteration. When the solution of the current relaxation is time feasible an optimal solution can be derived from it and the algorithm terminates. In this work we present new ideas, that allow for the propagation of information about the optimal solution of a coarser graph to a more refined graph and show how these can be used in algorithms, which are based on graph refinement. More precisely we present a new algorithm for solving Mixed Integer Linear Program (MILP) formulations of time-dependent problems that allows for the graph refinement to be carried out during the exploration of the branch-and-bound tree instead of restarting whenever the optimal solution was found to be infeasible. For demonstrating the practical relevance of this algorithm we present numerical results on its application to the shortest path problem with time-windows and the traveling salesman problem with time-windows. T3 - Cottbus Mathematical Preprints - 13, 2020 KW - Graphenverfeinerung KW - Branch-and-Bound KW - Kürzeste Wege Problem mit Zeitfenstern KW - Problem des Handlungsreisenden mit Zeitfenstern KW - Graph refinement KW - Branch-and-bound KW - Shortest path problem with time-windows KW - Travelling salesman problem with time-windows KW - Branch-and-Bound-Methode KW - Kürzester-Weg-Problem KW - Travelling-salesman-Problem Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-51995 SN - 2627-6100 ER - TY - JOUR A1 - Gnegel, Fabian A1 - Schaudt, Stefan A1 - Clausen, Uwe A1 - Fügenschuh, Armin T1 - A graph-refinement algorithm to minimize squared delivery delays using parcel robots JF - Mathematics N2 - In recent years, parcel volumes have reached record highs, prompting the logistics industry to explore innovative solutions to meet growing demand. In densely populated areas, delivery robots offer a promising alternative to traditional truck-based delivery systems. These autonomous electric robots operate on sidewalks and deliver time-sensitive goods, such as express parcels, medicine and meals. However, their limited cargo capacity and battery life require a return to a depot after each delivery. This challenge can be modeled as an electric vehicle-routing problem with soft time windows and single-unit capacity constraints. The objective is to serve all customers while minimizing the quadratic sum of delivery delays and ensuring each vehicle operates within its battery limitations. To address this problem, we propose a mixed-integer quadratic programming model and introduce an enhanced formulation using a layered graph structure. For this layered graph, we present two solution approaches based on relaxations that reduce the number of nodes and arcs compared to the expanded formulation. The first approach, Iterative Refinement, solves the current relaxation to optimality and refines the graph when the solution is infeasible for the expanded formulation. This process continues until a proven optimal solution is obtained. The second approach, Branch and Refine, integrates graph refinement into a branch-and-bound framework, eliminating the need for restarts. Computational experiments on modified Solomon instances demonstrate the effectiveness of our solution approaches, with Branch and Refine consistently outperforming Iterative Refinement across all tested parameter configurations. KW - Integer programming KW - Layered graph refinement KW - Delivery robots KW - Electric vehicle-routing problem KW - Partial recharging Y1 - 2024 U6 - https://doi.org/10.3390/math12203201 SN - 2227-7390 VL - 12 PB - MDPI CY - Basel ER -