TY - CHAP ED - Beisegel, Jesse ED - Scheffler, Robert ED - Köhler, Ekkehard T1 - Book of open problems : 11th workshop on graph classes, optimization, and width parameters (GROW 2024) T1 - Sammlung offener Probleme : 11. Workshop über Graphenklassen, Optimierung und Weiteparameter (GROW 2024) N2 - The Workshop on Graph Classes, Optimization, and Width Parameters (GROW) series of workshops brings together experts in both theoretical and practical issues to design new strategies for dealing with intractable graph problems. Its 11th edition, GROW 2024, was hosted by the Brandenburg University of Technology, Faculty of Mathematics, Computer Science, Physics, Electrical Engineering and Information Technology, Cottbus, Germany, from September 9–12, 2024. This booklet contains descriptions of open problems presented at GROW 2024. N2 - Die Workshop-Reihe „Graph Classes, Optimization, and Width Parameters“ (GROW) bringt Experten für theoretische und praktische Fragestellungen zusammen, um neue Strategien für den Umgang mit schwer lösbaren Graphenproblemen zu entwickeln. Die 11. Ausgabe, GROW 2024, wurde vom 9. bis 12. September 2024 von der BTU Cottbus-Senftenberg, Fakultät für Mathematik, Informatik, Physik, Elektro- und Informationstechnik, Cottbus, Deutschland, ausgerichtet. Diese Sammlung enthält Beschreibungen offener Probleme, die bei der GROW 2024 vorgestellt wurden. KW - Graph theory KW - Graph classes KW - Graph parameters KW - Graph algorithms KW - Graphenalgorithmen KW - Graphklassen KW - Graphparameter KW - Graphentheorie KW - Graphentheorie Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-71295 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Inter-sample avoidance in trajectory planning via an integer-polytope formulation for mixed-integer optimization T1 - Vermeidung von Kollisionen zwischen diskreten Zeitpunkten in der Trajektorienplanung mittels eines ganzzahligen Polytops für gemischt-ganzzahlige Optimierungsprobleme N2 - Autonomous vehicles such as drones or mobile robots must plan trajectories that avoid static obstacles. Their dynamics are captured by Newton’s laws and discretized numerically, so the vehicle’s position is tracked only at finitely many sample points. The resulting information gap allows a path to cut through an obstacle while still appearing feasible at all samples, a phenomenon called corner cutting. Finer time grids mitigate but never eliminate this artefact and increase computation time. We propose a new inter-sample avoidance scheme for polyhedral obstacles. The facet-defining half-spaces partition the three-dimensional mission space into sub-domains that we encode with binary sign vectors. Feasible one-step moves correspond to a specific subset of these vectors; we (i) enumerate that set exhaustively and (ii) give an integer-polytope formulation that enforces it without additional state variables or extra time steps. For planar motion with a single triangular no-fly zone we prove that the formulation is tight-the polytope equals the convex hull of its 0/1 points. The method is compared qualitatively with existing inter-sample avoidance techniques and its limitations are discussed. Computational experiments with a mixed-integer linear programming model for UAV mission planning, solved by Gurobi, demonstrate that the new formulation achieves realistic trajectories at competitive, or lower, solution times. N2 - Autonome Fahrzeuge wie Drohnen oder mobile Roboter müssen Routen planen, die statische Hindernisse umgehen. Ihre Dynamik wird durch die Newtonschen Gesetze erfasst und numerisch diskretisiert, sodass die Position des Fahrzeugs nur an einer endlichen Anzahl von Zeitpunkten verfolgt wird. Die daraus resultierende Informationslücke ermöglicht es, dass eine Route ein Hindernis durchschneidet und dennoch zu allen Zeitpunkten als machbar erscheint – ein Phänomen, das als „Corner Cutting“ bezeichnet wird. Feinere Zeitraster mildern dieses Artefakt, können es jedoch nie vollständig beseitigen und erhöhen zudem die Rechenzeit. Wir schlagen ein neues Schema zur Vermeidung von Hindernissen zwischen den Zeitpunkten für polyedrische Hindernisse vor. Die facettendefinierenden Halbräume unterteilen den dreidimensionalen Missionsraum in Teilgebiete, die wir mit binären Vorzeichenvektoren kodieren. Machbare Ein-Schritt-Bewegungen entsprechen einer bestimmten Teilmenge dieser Vektoren; wir (i) zählen diese Menge vollständig auf und (ii) geben eine ganzzahlige Polytopformulierung an, die sie ohne zusätzliche Zustandsvariablen oder zusätzliche Zeitschritte sicherstellt. Für planare Bewegungen mit einer einzigen dreieckigen Flugverbotszone beweisen wir, dass die Formulierung effizient ist – das Polytop entspricht der konvexen Hülle seiner 0/1-Punkte. Die Methode wird qualitativ mit bestehenden Techniken zur Vermeidung von Hindernissen zwischen den Zeitpunkten verglichen und ihre Grenzen werden diskutiert. Rechenexperimente mit einem gemischt-ganzzahligen linearen Optimierungsmodell für die Missionsplanung von UAVs, gelöst von Gurobi, zeigen, dass die neue Formulierung realistische Routen bei konkurrenzfähigen oder niedrigeren Rechenzeiten erzielt. T3 - Cottbus Mathematical Preprints - 34, 2025 KW - Mixed-integer optimization KW - Inter-sample avoidance KW - Trajectory planning KW - Convex hull KW - Unmanned aerial vehicles KW - Gemischt-ganzzahlige Optimierung KW - Trajektorienplanung KW - Konvexe Hülle KW - Unbemannte Luftfahrzeuge KW - Drohne (Flugkörper) KW - Autonomes System KW - Bahnplanung KW - Gemischt-ganzzahlige Optimierung KW - Konvexe Hülle Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-71697 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin A1 - Böschow, Moritz M. T1 - Sports league scheduling with minitournaments T1 - Planung von Sportligen mit Miniturnieren N2 - In amateur or youth sports leagues, the teams play all matches during their leisure time. Thus, a schedule with a smaller number of game days is preferred and the teams are willing to partly renounce on the fairness for this by playing minitournaments instead of single matches. In this format, multiple teams meet at one of them and play against each other, reducing the number of necessary game days and required referees at the cost of unevenly distributed home field advantages. The travel times of all teams now depend on their assignment to the respective minitournaments and the choice of the home team. We present a binary linear optimization model to schedule a sports league as a double Round Robin tournament with minitournaments and most evenly distributed home field advantages, yielding a feasible league schedule with minimal total traveling distances for all teams. After adjusting orbital shrinking to break the occurring symmetries in the possible assignments, we discuss the computational efficiency and evaluate an existing schedule for the "Basketball Senioren Landesliga Brandenburg" amateur basketball league in Germany. N2 - In Amateur- oder Jugendsportligen tragen die Mannschaften alle Spiele in ihrer Freizeit aus. Daher wird ein Spielplan mit einer geringeren Anzahl von Spieltagen bevorzugt, und die Mannschaften sind bereit, dafür teilweise auf die Fairness zu verzichten, indem sie Miniturniere anstelle von Einzelspielen spielen. Bei diesem Format treffen sich mehrere Mannschaften an einem Spieltag und spielen gegeneinander, wodurch die Anzahl der notwendigen Spieltage und der benötigten Schiedsrichter reduziert wird, allerdings auf Kosten eines ungleich verteilten Heimvorteils. Die Reisezeiten aller Mannschaften hängen nun von ihrer Zuordnung zu den jeweiligen Miniturnieren und der Wahl der Heimmannschaft ab. Wir stellen ein binäres lineares Optimierungsmodell vor, um eine Sportliga als doppeltes Round-Robin-Turnier mit Miniturnieren und möglichst gleichmäßig verteilten Heimvorteilen zu planen. Das Ziel ist ein zulässiger Ligaplan mit minimalen Gesamtreisezeiten für alle Mannschaften. Nach der Anpassung der "orbital shrinking"-Methode, um die auftretenden Symmetrien in den möglichen Zuordnungen zu brechen, diskutieren wir die rechnerische Effizienz und evaluieren einen bestehenden Spielplan für die Basketball Senioren Landesliga Brandenburg in Deutschland. T3 - Cottbus Mathematical Preprints - 33, 2025 KW - Discrete optimization KW - Linear optimization KW - Orbital shrinking KW - Sport scheduling KW - Diskrete Optimierung KW - Lineare Optimierung KW - Sportligenplanung KW - Lineare Optimierung KW - Diskrete Optimierung KW - Wettkampfklasse KW - Amateursport KW - Jugendsport KW - Spielplan Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-70293 ER - TY - RPRT A1 - Zell, Sascha A1 - Fügenschuh, Armin T1 - Optimizing autonomous unmanned aircraft system deployment locations for enhanced wildfire detection and monitoring T1 - Standortoptimierung autonomer unbemannter Flugsysteme zur fortgeschrittenen Erkennung und Beobachtung von Waldbränden N2 - The increase in the frequency and severity of wildfires as a symptom of climate change requires innovative methods of wildfire fighting. For this reason, we propose a framework for an autonomous Unmanned Aircraft System (UAS), consisting of a fleet of Micro Air Vehicles (MAVs) stored in purpose-built hangars. The intention is to deploy the UAS as the first responder to an alarm and have the sensor-equipped MAVs monitor the target area even before other standard firefighting vehicles have arrived. The focus of this paper is primarily on the development and application of a location-allocation optimization Mixed-Integer Linear Programming (MILP) model that selects different MAV and hangar types and locates them, with the objective of approaching the target area as quickly as possible while guaranteeing a certain monitoring time at the scene. The model is applied to a large, sparsely populated, rural operational area, around a third of which consists of forest in the South of Brandenburg, Germany. The spatial demand is measured through an easily reproducible and transferable open data approach. Finally, several instances with different fixed numbers of hangars and MAVs to be set up are solved by the commercial state-of-the-art solver CPLEX and analyzed for their computation time. N2 - Die Zunahme der Häufigkeit und Schwere von Waldbränden als Symptom des Klimawandels erfordert innovative Methoden der Waldbrandbekämpfung. Für diesen Zweck nutzen wir ein autonomes unbemanntes Luftfahrtsystem (Unmanned Aricraft System - UAS), das aus einer Flotte von Drohnen besteht, die in eigens dafür errichteten Hangars gelagert werden. Ziel ist, das UAS als Erstreaktion bei einem Alarm einzusetzen und die mit Sensoren ausgestatteten Drohnen das Zielgebiet beobachten zu lassen, noch bevor die ersten Einsatzkräfte vor Ort eintreffen. Der Fokus dieses Papers liegt in erster Linie auf der Entwicklung und Anwendung eines Modells der gemischt-ganzzahligen Programmierung (Mixed-Integer Linear Programming - MILP) zur Optimierung der Standortzuweisung. Es werden verschiedene Drohnen- und Hangartypen auswählt und platziert, mit dem Ziel, die Einsatzbereiche so schnell wie möglich anzufliegen und gleichzeitig eine bestimmte Beobachtungszeit am Einsatzort zu garantieren. Das Modell wird auf ein großes, dünn besiedeltes, ländliches Einsatzgebiet, das zu etwa einem Drittel aus Wald besteht, im Süden von Brandenburg, Deutschland angewendet. Die räumliche Nachfrage wird durch einen leicht reproduzierbaren und übertragbaren Ansatz mittels Open Data gemessen. Schließlich werden mehrere Instanzen mit unterschiedlichen festgelegten Anzahlen von Hangars und aufzustellenden MAVs mit dem kommerziellen State-of-the-Art Solver CPLEX gelöst und auf ihre Rechenzeit hin analysiert. T3 - Cottbus Mathematical Preprints - 32, 2025 KW - Mixed-lnteger linear programming KW - Unmanned aircraft systems KW - Micro air vehicles KW - Autonomous wildfire monitoring KW - Location-allocation optimization KW - Gemischt-ganzzahlige Programmierung KW - Drohnen KW - Drohnenhangar KW - Standortproblem KW - Autonome Waldbrandbekämpfung KW - Waldbrand KW - Überwachung KW - Drohne (Flugkörper) KW - Autonomes System KW - Standortproblem KW - Lineare Optimierung Y1 - 2025 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-69422 N1 - This paper is a preprint that will be published as a post-conference proceedings of the Optimization and Wildfire Conference (O&W) that took place in Luso, Portugal, 2024 in "Lecture Notes in Operations Research" by Springer. https://doi.org/10.1007/978-3-032-03108-2 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 - TY - RPRT A1 - Zell, Sascha A1 - Schneidereit, Toni A1 - Fügenschuh, Armin A1 - Breuß, Michael T1 - Advanced search and rescue operations for drowning swimmers using autonomous unmanned aircraft systems : location optimization, flight trajectory planning and image-based localization T1 - Fortgeschrittene Such- und Rettungseinsätze für ertrinkende Schwimmer mit autonomen unbemannten Flugsystemen : Standortoptimierung, Flugtrajektorienplanung und bildgestützte Lokalisierung N2 - Drowning is among the most prevalent causes of death from unintentional injuries worldwide. Because of the time-sensitive nature of swimming accidents and the shortage of lifeguard staff resulting in unsupervised swimming areas, interest in supportive rescue methods increases. In this paper, we propose an autonomous Unmanned Aircraft System (UAS) usable by Emergency Medical Service (EMS) providers in swimmer rescue scenarios additionally to Standard Rescue Operation (SRO) equipment. The UAS consists of Unmanned Aerial Vehicles (UAVs) and purpose-built hangars located near the swimming area to store the UAVs. When receiving an alert, the UAVs autonomously navigate to the emergency site to conduct a Search and Rescue (S&R) operation for the drowning person. We introduce a Mixed-Integer Linear Programming (MILP) model to address the Facility Location Problem (FLP), assisting with identification of accessibility-optimal UAV hangar placements near the swimming area. Additionally, we present a MILP model to optimize the UAV flight trajectories in advance of the operation, allowing for efficient coordination of a heterogeneous UAV fleet. We apply the presented MILP models to a real-world scenario in the Lusatian Lake District using the state-of-the-art commercial solver CPLEX to solve the instances. Furthermore, we present a method for automated image-based swimmer localization using the state-of-the-art neural network You Only Look Once (YOLO). Finally, we use a Discrete-Event Simulation (DES) approach to quantify how much time is saved by using additional resources. N2 - Ertrinken ist weltweit eine der häufigsten Todesursachen durch unbeabsichtigte Verletzungen. Aufgrund der zeitkritischen Natur von Badeunfällen und des Personalmangels an Rettungsschwimmern, der in vielen unbewachten Badegebieten resultiert, steigt das Interesse an unterstützenden innovativen Rettungsmethoden. In diesem Beitrag stellen wir ein autonomes unbemanntes Luftfahrzeugsystem (Unmanned Aircraft System - UAS) vor, das von Rettungsdiensten bei der Rettung von Schwimmern zusätzlich zu Standard-Rettungsmitteln eingesetzt werden kann. Das UAS besteht aus unbemannten Luftfahrzeugen (Unmanned Aerial Vehicles - UAVs) und speziell angefertigten Hangars, die in der Nähe des Schwimmbereichs aufgestellt werden, um darin die UAVs zu lagern. Sobald ein Alarm eingeht, navigieren die UAVs autonom zum Unfallort, um eine Such- und Rettungsaktion (Search and Rescue - S&R) für die ertrinkende Person durchzuführen. Wir stellen ein gemischt-ganzzahliges lineares Programm (Mixed-Integer Linear Program - MILP) vor, um das Standortproblem (Facility Location Problem - FLP) zu lösen, welches die Identifizierung zeitoptimaler UAV-Hangarstandorte in der Nähe des Schwimmbereichs ermöglicht. Außerdem stellen wir ein MILP zur Optimierung von Flugtrajektorien der UAVs im Vorfeld der Mission vor, was eine effiziente Koordination einer heterogenen UAV-Flotte ermöglicht. Wir wenden die vorgestellten MILP-Modelle auf ein reales Szenario im Lausitzer Seenland an und verwenden den modernen kommerziellen Löser CPLEX, um Optimallösungen der Instanzen zufinden. Darüber hinaus stellen wir eine Methode zur automatischen bildbasierten Lokalisierung von Schwimmern vor, die das moderne neuronale Netzwerk You Only Look Once (YOLO) verwendet. Schließlich verwenden wir ereignisorientierte Simulation (Discrete-Event Simulation - DES), um zu quantifizieren, wie viel Zeit durch die Verwendung zusätzlicher Ressourcen eingespart wird. T3 - Cottbus Mathematical Preprints - 31, 2024 KW - Unmanned Aerial Vehicle KW - Unmanned Aircraft System KW - Water Rescue KW - Mixed-Integer Linear Programming KW - You Only Look Once KW - Drohne KW - Drohnenhangar KW - Wasserrettung KW - Gemischt-ganzzahlige Programmierung KW - Standortoptimierung KW - Drohne KW - Wasserrettung KW - Lineare Optimierung Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-68669 ER - TY - THES A1 - Schmidt, Johannes T1 - The mission and flight planning problem : a physics-based MILP routing approach for an inhomogeneous fleet of unmanned aerial vehicles with collision-free trajectories T1 - Das Missions- und Flugplanungsproblem : Ein physik-basierter, gemischt-ganzzahlig linearer Routenplanungsansatz für eine inhomogene Flotte unbemannter Luftfahrzeuge mit kollisionsfreien Trajektorien N2 - Today, drones are a helpful addition or even an efficient alternative in many areas due to their simple control and low operating costs compared to manned aircraft. Often, it is preferred that the UAV performs its mission autonomously. Thus, next to the operative control, the strategic planning of such missions plays an important role for their efficiency. Furthermore, it is also of interest for air traffic management to integrate UAVs into the airspace of manned aviation. At a strategic level, many use cases can be represented by a set of waypoints. Maybe not all of them can be visited within a given time horizon or only by drones with special hardware. Thus, before the start of a mission, each involved UAV must be assigned the waypoints to be processed and its flight trajectory must be planned to guarantee a safe and efficient process. These two sub-problems of the planning process influence each other and cannot be treated separately. In this paper, we address this problem by introducing the Mission and Flight Planning Problem (MFPP). Therein, the assignment of the UAVs to the given waypoints is combined with the computation of exact flight trajectories in a mixed-integer linear optimization problem (MILP). It is based on a team orienteering problem with time windows, in which the positions of all UAVs are calculated using discretized Newton's laws of motion. Concerning the flight dynamics, design-related parameters and mass, speed, and altitude dependencies of the performance data of each drone are included in the model. Each drone is controlled by radio and must not leave the range of its control station. There may be obstacles within the mission area. The UAVs must also maintain safety distances from each other to avoid collisions. In addition to the model, we discuss different types of valid inequalities. We present a new inter-sample avoidance approach based on decomposing the mission area into several sub-areas and their identification with binary vectors. The construction of an integer polyhedron containing these binary vectors is given and we investigate its structure. In addition, different possibilities for implementing the new constraints are discussed. For two special types of MFPP instances, we present adapted solution methods that exploit their respective structure, i.e., a sequential solution method and a column generation approach. The performance of the presented model is investigated in detailed computational studies and we discuss its essential properties in several examples. N2 - Heute sind Drohnen, aufgrund ihrer einfachen Steuerung und geringen Einsatzkosten im Vergleich zu bemannten Luftfahrzeugen, eine hilfreiche Ergänzung oder sogar eine effiziente Alternative in vielen Bereichen. Oft soll der Einsatz der Drohne dabei autonom erfolgen. Deshalb spielt neben dem operativen Betrieb auch die strategische Planung solcher Missionen für ihre effiziente Ausführung eine wesentliche Rolle. Weiterhin ist sie auch für die Flugsicherung von großem Interesse, um UAVs sicher in den Luftraum der bemannten Luftfahrt zu integrieren. Auf einer strategischen Ebene lassen sich viele Anwendungsfälle mit Hilfe einer Menge von Wegpunkten darstellen. Von diesen können eventuell nicht alle innerhalb eines gegebenen Zeithorizonts oder nur von Drohnen mit spezieller Ausrüstung besucht werden. Somit müssen vor dem Start einer Mission jeder beteiligten Drohne die von ihr zu bearbeitenden Wegpunkte zugewiesen und ihre Flugtrajektorie geplant werden, um einen sicheren und effizienten Ablauf zu garantieren. Diese beiden Teilprobleme des Planungsprozesses beeinflussen sich gegenseitig und können nicht losgelöst voneinander behandelt werden. In dieser Arbeit begegnen wir diesem Problem, indem wir das Missions- und Flugplanungsproblem (MFPP) einführen. Darin wird die Zuordnung der UAVs zu den gegebenen Wegpunkten mit der Berechnung exakter Flugtrajektorien in einem linearen, gemischt-ganzzahligen Optimierungsproblem kombiniert. Die Grundlage dafür ist ein "Team Orienteering"- Problem mit Zeitfenstern, in welchem die Positionen aller UAVs mit Hilfe der diskretisierten Newton'schen Bewegungsgesetze berechnet werden. Bezüglich der Flugdynamik werden bauartbedingte Parameter und Masse-, Geschwindigkeits-, sowie Höhenabhängigkeiten der Leistungskennzahlen jeder Drohne in das Modell einbezogen. Jede Drohne wird per Funk gesteuert und kann sich nicht außerhalb der Reichweite ihrer Kontrollstation bewegen. Innerhalb des Missionsgebietes können sich Hindernisse befinden. Außerdem müssen die UAVs untereinander Sicherheitsabstände zur Kollisionsvermeidung einhalten. Zusätzlich zum Modell diskutieren wir auch verschiedene Arten von gültigen Ungleichungen. Wir präsentieren einen neuen Modellierungsansatz zur Kollisionsvermeidung zwischen Zeitschritten, basierend auf der Zerlegung des Missionsgebietes in mehrere Teilgebiete und deren Identifikation mit Binärvektoren. Die Konstruktion eines ganzzahligen Polyeders, welches diese Binärvektoren enthält, wird angegeben und wir untersuchen seine Struktur. Zudem werden verschiedene Möglichkeiten zur Implementierung der neuen Nebenbedingungen diskutiert. Für zwei spezielle Typen von MFPP-Instanzen präsentieren wir angepasste Lösungsmethoden, die sich deren Struktur zu Nutze machen, einen sequenziellen Lösungsansatz und Spaltengenerierung. Die Performanz des vorgestellten Modells wird in ausführlichen Berechnungsstudien untersucht und wir diskutieren an verschiedenen Beispielen seine wesentlichen Eigenschaften. T3 - Cottbus Mathematical Preprints - 30, 2024 KW - Mixed-integer linear programming KW - Trajectory optimization KW - Inter-sample avoidance KW - Unmanned aerial vehicles KW - Gemischt-ganzzahlige lineare Programmierung KW - Trajektorienoptimierung KW - Kollisionsvermeidung zwischen Zeitschritten KW - Unbemannte Luftfahrzeuge KW - Flugkörper KW - Optimierungsproblem KW - Strategische Planung KW - Kollisionsschutz KW - Trajektorie Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-68415 ER - TY - THES A1 - Zhong, Lingyu T1 - Set Covering Probleme in der Funknetzplanung T1 - Set covering problems in radio network planning N2 - In dieser Bachelorarbeit wird das Problem der Auswahl von Antennenstandorten für eine maximale räumliche Abdeckung in 5G-Funknetzen untersucht. Das Hauptziel besteht darin, eine effiziente Lösung für dieses kombinatorische Optimierungsproblem zu finden, indem es als Partial Set Covering Problem formuliert und gelöst wird. Die Arbeit gliedert sich in zwei Teile: Der erste Teil bietet eine Einführung in die mathematischen Grundlagen des Partial Set Covering Problems, einschließlich Definitionen, Formulierung und Lösungsverfahren. Im zweiten Teil wird ein praktischer Ansatz zur Lösung dieses Problems präsentiert, wobei realen Instanzen für die Auswahl von Antennenstandorten analysiert werden. Hierbei werden zwei Hauptfragen untersucht: 1) Wie kann die gegebene Instanz in ein Partial Set Covering Problem umformuliert werden? 2) Wie kann dieses Problem mithilfe eines heuristischen Verfahrens, insbesondere des Simulated-Annealing-Algorithmus, gelöst werden? Die Ergebnisse dieser Arbeit tragen dazu bei, fundierte Entscheidungen über den Aufbau von 5G-Netzen zu treffen und die Netzwerkabdeckung unter Berücksichtigung von Nebenbedingungen zu maximieren. N2 - This bachelor thesis examines the problem of selecting antenna sites for maximum spatial coverage in 5G radio networks. The main goal is to find an efficient solution to this combinatorial optimization problem by formulating and solving it as a partial set covering problem. The thesis is divided into two parts: The first part provides an introduction to the mathematical foundations of the Partial Set Covering Problem, including definitions, formulation and solution methods. In the second part, a practical approach to solve this problem is presented, analyzing real instances for antenna site selection. Two main questions are examined here: 1) How can the given instance be reformulated into a partial set covering problem? 2) How can this problem be solved using a heuristic method, in particular the simulated annealing algorithm? The results of this work help to make informed decisions about building 5G networks and to maximize network coverage considering constraints. T3 - Cottbus Mathematical Preprints - 29, 2023 KW - 5G-Funknetze KW - Antennenstandort-Optimierung KW - Kombinatorische Optimierung KW - Partial Set Covering Problem KW - Simulated-Annealing-Algorithmus KW - 5G radio networks KW - Antenna site optimization KW - Combinatorial optimization KW - Partial set covering problem KW - Simulated annealing algorithm KW - 5G KW - Funknetz KW - Antenne KW - Kombinatorische Optimierung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-63556 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Trajectory optimization for arbitrary layered geometries in wire-arc additive manufacturing T1 - Trajektorienoptimierung für beliebige Schichtgeometrien in der additiven Draht-Lichtbogen-Fertigung N2 - In wire-arc additive manufacturing, a wire is molten by an electrical or laser arc and deposited droplet-by-droplet to construct the desired workpiece, given as a set of two-dimensional layers. The weld source can move freely over a substrate plate, processing each layer, but there is also the possibility of moving without welding. A primary reason for stress inside the material is the large thermal gradient caused by the weld source, resulting in lower product quality. Thus, it is desirable to control the temperature of the workpiece during the process. One way of its optimization is the trajectory of the weld source. We consider the problem of finding a trajectory of the moving weld source for a single layer of an arbitrary workpiece that maximizes the quality of the part and derive a novel mixed-integer PDE-constrained model, including the calculation of a detailed temperature distribution measuring the overall quality. The resulting optimization problem is linearized and solved using the state-of-the-art numerical solver IBM CPLEX. Its performance is examined by several computational studies. N2 - Bei der additiven Draht-Lichtbogen-Fertigung wird ein Draht durch einen Licht- oder Laserlichtbogen geschmolzen und Tropfen für Tropfen aufgebracht, um das gewünschte Werkstück aus zweidimensionalen Schichten aufzubauen. Die Schweißquelle kann sich frei über eine Substratplatte bewegen und jede Schicht bearbeiten; zudem besteht auch die Möglichkeit, sich ohne Schweißen zu bewegen. Ein Hauptgrund für Spannungen im Material ist der große Wärmegradient, der durch die Schweißquelle verursacht wird, was zu einer geringeren Produktqualität führt. Daher ist es wünschenswert, die Temperatur des Werkstücks während des Prozesses zu steuern. Eine Möglichkeit dafür ist die Trajektorie der Schweißquelle. Wir betrachten das Problem, eine Trajektorie der sich bewegenden Schweißquelle für eine einzelne Schicht eines beliebigen Werkstücks zu finden, die die Qualität des Teils maximiert, und leiten ein neuartiges gemischt-ganzzahliges PDE-beschränktes Modell ab, einschließlich der Berechnung einer detaillierten Temperaturverteilung, welche zur Beurteilung der Gesamtqualität benötigt wird. Das resultierende Optimierungsproblem wird linearisiert und mit dem aktuellen numerischen Löser IBM CPLEX gelöst. Die Performanz wird in mehreren Rechenstudien untersucht. T3 - Cottbus Mathematical Preprints - 28, 2023 KW - Mixed-integer programming KW - Trajektorie KW - Partielle Differentialgleichung KW - Finite-Volumen-Methode KW - Wärmeleitung KW - Wire are additive manufacturing KW - Trajectory planning KW - Partial differential equations KW - Finite element method KW - Heat conduction KW - Gemischt-ganzzahlige Programmierung KW - Additive Draht-Lichtbogen-Fertigung, KW - Trajektorienplanung KW - Partielle Differenzialgleichungen KW - Finite-Elemente-Methode KW - Wärmeleitung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-62678 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 - THES A1 - Stieber, Anke ED - Fügenschuh, Armin T1 - The multiple traveling salesperson problem with moving targets T1 - Das multiple Handlungsreisendenproblem mit beweglichen Zielen N2 - Military installations and objects in out-of-area missions, e.g., an air base or a field camp, must be protected from incoming hostile rockets, artillery or mortar fire. Lasers as directed energy weapons are able to destroy those targets within seconds. Generally, the laser is assigned to a target, that applies the smallest movement of its direction unit to aim at it. The goal is to minimize the damage and thus, to destroy all incoming targets. We model the problem as a multiple traveling salesperson problem with moving targets, where the salespersons correspond to the lasers. The targets move over time on continuous trajectories. Additionally, each target is given a visibility time window. We investigate if exact methods are able to solve real-world instances in reasonable time. On that account, we address the problem from two sides, offline and online. One essential aspect studied in this work is to find an appropriate formulation to model the time requirements. We present five different modeling approaches, where the time aspect is handled in different ways: discrete, continuous, directly or via sub-problems. Our randomly generated test instances consider 6 to 20 targets and 1 to 6 salespersons. Computational experiments with linear and non-linear trajectories are performed. The best model can solve instances up to 10 targets within 3 seconds. For online experiments the two familiar strategies REPLAN and IGNORE are adapted to our problem. Another important aspect of this work is our contribution to competitive analysis, a method to evaluate the quality of online algorithms. Here, we restrict the problem considered so far to one salesperson and address the online moving targets traveling salesperson problem on the real line. We prove a lower bound for the competitive ratio regarding this problem. Then, we develop an online algorithm and present its competitive ratio with the corresponding proof. The competitive ratio depends on the speed ratio of salespersons and targets and outperforms a comparable online algorithm from the literature for certain speed ratios. The theoretical results obtained for the online moving target traveling salesperson problem on the real line are new in this research area. N2 - Bei militärischen Operationen und Auslandseinsätzen ist es notwendig, die verwendete Infrastruktur sowie militärische Objekte, wie beispielsweise Militärflugplätze oder Feldlager vor feindlichem Beschuss zu schützen. Laserwaffen können diese feindlichen Geschosse (Ziele) in Sekundenschnelle neutralisieren. Zur Abwehr eines Zieles wird derjenige Laser ausgewählt, der die Zerstörung des Zieles mit geringster Bewegung der Strahlführungseinheit ermöglicht. Es sollen möglichst alle Ziele eliminiert werden. In der vorliegenden Arbeit wird diese Anwendung als multiples Handlungsreisendenproblem mit beweglichen Zielen beschrieben, wobei die Laser als Verfolger fungieren, welche die Ziele in bestimmten Zeitfenstern besuchen müssen. Die Ziele bewegen sich kontinuierlich über der Zeit auf sogenannten Trajektorien (Flugbahnen). Der Fokus der Arbeit liegt darauf, zu untersuchen, ob exakte Verfahren in der Lage sind, reale Instanzen adäquat schnell zu lösen. Dazu betrachten wir das Problem zuerst offline und anschließend online. Ein zentraler Aspekt dieser Arbeit ist es, den Zeitaspekt geeignet zu modellieren. In diesem Zusammenhang werden fünf verschiedene Modelle vorgestellt, die zum einen auf einer diskreten oder kontinuierlichen Zeitrepräsentation basieren und zum anderen die Zeitzulässigkeit direkt oder über Unterprogramme realisieren. Die zufällig generierten Testinstanzen berücksichtigen 6 bis 20 Ziele und 1 bis 6 Verfolger. Das beste Modell löst offline-Instanzen mit bis zu 10 Zielen im Schnitt innerhalb von 3 Sekunden. Die Tests berücksichtigen sowohl lineare als auch nicht-lineare Trajektorien. Für die Online-Experimente werden bekannte Update-Strategien (REPLAN, IGNORE) adaptiert. Ein weiterer wichtiger Teil dieser Arbeit ist der Beitrag zur Kompetitivitätsanalyse, einer Methode zur Bewertung von Online-Algorithmen. Dazu beschränken wir uns auf einen Verfolger und betrachten das Online-Traveling-Salesperson-Problem mit sich bewegenden Zielen auf der reellen Zahlengeraden. Zu diesem Problem wird eine untere Schranke für den Kompetitivitätsfaktor angegeben. Außerdem präsentiert diese Arbeit einen Online-Algorithmus und den Beweis seines Kompetitivitätsfaktors. Dieser ist abhängig vom Geschwindigkeitsverhältnis von Verfolger und Zielen und für bestimmte Geschwindigkeitsverhältnisse besser als der eines vergleichbaren Online-Algorithmus aus der Literatur. Die erzielten theoretischen Resultate zum Online-Handlungsreisendenproblem mit beweglichen Zielen auf der reellen Zahlengeraden stellen neue Ergebnisse in diesem Bereich dar. T3 - Cottbus Mathematical Preprints - 26, 2022 KW - Multiple traveling salesperson problem KW - Moving targets KW - Modeling of time KW - Online algorithms KW - Competitive analysis KW - Multiples Handlungsreisendenproblem KW - Bewegliche Ziele KW - Modellierung von Zeit KW - Online-Algorithmen KW - Kompetitivitätsanalyse KW - Competitive analysis KW - Travelling-salesman-Problem Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-61104 ER - TY - THES A1 - Zell, Sascha T1 - Agentenbasierte Modellierung und Simulation der Rettungskette : eine Fallstudie in der Lausitz T1 - Agent based modelling and simulation of the rescue chain N2 - A functioning prehospital Emergency Medical Service (EMS) system is of special importance for society and subject to many new challenges of present time. Socioeconomic change and technical progress affect existing systems and force responsibles to adopt new approaches for performance optimization. Therefore this work provides a literature review on different EMS planning problems and presents an agent-based simulation approach to model the rescue chain of a region specific EMS system. Underlying data from urban region Cottbus, Brandenburg, Germany is used to parameterize and verify the model. Using a geographic information system (GIS), the model generates emergency calls according to population density with a time dependent rate and displays different key figures for evaluation of system performance. A graphical interface including operation and statistics monitoring was designed to lay the foundation for practical application. N2 - Ein funktionierender Rettungsdienst ist für die Gesellschaft von zentraler Bedeutung, da in medizinischen Notsituationen die Gesundheit eines Verunfallten von der Qualität der praäklinischen medizinischen Versorgung abhängt. Dabei steht man vor immer neuen Herausforderungen des sozioökonomischen Wandels und technischen Fortschritts, die neue Ansätze zur Systemoptimierung erfordern. Diese Arbeit beinhaltet eine Literaturübersicht über Planungsprobleme, sowie eine Klassifizierung von Emergency Medical Service (EMS) Systemen. Ein agentenbasiertes Simulationsmodell für ein notarztbasiertes EMS-System wird vorgestellt und auf die Rettungskette eines städtischen Gebietes Cottbus, Brandenburg, Deutschland angewandt. Die Parametrisierung des Modells erfolgt durch zugrundeliegende Einsatzdaten, dabei wird ein Geoinformationssystem (GIS) genutzt, Notrufe über die Bevölkerungsdichte mit einer zeitabhängigen Rate generiert und statistische Kenngrößen des Systems ausgewertet. Das in AnyLogic implementierte Simulationsmodell enthält eine graphische Nutzeroberfläche, in der Einsatzdetails und Statistiken als Grundlage für Anwendungen in der Praxis angezeigt werden. T3 - Cottbus Mathematical Preprints - 25, 2022 KW - Emergency medical service system KW - Agent-based simulation KW - Rescue chain KW - Rettungsdienst KW - Rettungskette KW - Agentenbasiertes Simulationsmodell KW - Cottbus KW - Rettungswesen KW - Geoinformationssystem KW - Simulation Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-58731 ER - TY - THES A1 - Werger, Tabea T1 - Instandhaltungsprogramm - NH90 : ein ganzzahliger Ansatz zur Optimierung des Instandhaltungsprogramms eines militärischen Luftfahrzeugs T1 - Maintenance programme - NH90 : an integer approach for optimizing the maintenance program of a military aircraft N2 - Die vorliegende Arbeit untersucht die Instandhaltungsplanung eines militärischen Luftfahrzeugs. Das Ziel ist die Eingliederung aller Instandhaltungsaufgaben des Luftfahrzeugs in Wartungsintervalle, die durch das aktuelle Instandhaltungsprogramm festgelegt sind. Dieses besteht aus bereits gemäß ihrer Frist paketierten Instandhaltungsaufgaben und aus nicht zugeordneten Aufgaben, welche im Folgenden betrachtet werden. Gegenstand der Untersuchung sind die Arbeitsdauer und die Frist der Instandhaltungsaufgaben. Die nicht paketierten Instandhaltungsaufgaben sollen so zugeordnet werden, dass der Arbeitsaufwand und die verlorenen Tage, die durch das Vorziehen von Instandhaltungsaufgaben entstehen, auf ein Minimum reduziert werden. Dafür wird ein multikriterielles, ganzzahliges Optimierungsmodell entwickelt. Zum Lösen wird der Solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) verwendet. In der Auswertung wird zusätzlich zu den Ergebnissen der Optimierung die Auswirkung von aggregierten und disaggregierten Formulierungen untersucht sowie der Effekt von Veränderungen der Aggressivität von Schnittebenenverfahren. N2 - The following work examines the maintenance planning of a military aircraft. The goal is the integration of all maintenance tasks of the aircraft into maintenance intervals, which are defined by the current maintenance program. The totality of the maintenance tasks consists of the already packaged tasks and those yet to be assigned. The considered factors for the assignment are the working time and the deadline of the tasks. The unpackaged maintenance tasks are to be assigned such that the workload and the lost days caused by early execution of maintenance tasks are reduced to a minimum. For this purpose a multiobjective integer optimization model was developed. The solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) was used for solving. In addition to the general results of the optimization approach, the disparities of aggregated and disaggregated formulations were studied. Further, the consequences of altering the aggressiveness of cutting plane methods were analysed. T3 - Cottbus Mathematical Preprints - 24, 2022 KW - Gemischt-ganzzahlige Optimierung KW - Hubschrauber KW - Instandhaltung KW - Planung KW - Schnittebenenverfahren KW - Mixed-integer optimization KW - Helicopter KW - Maintenance KW - Planning KW - Cutting plane method KW - Gemischt-ganzzahlige Optimierung KW - Schnittebenenverfahren KW - Instandhaltungsplanung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-58724 ER - TY - RPRT A1 - Beisegel, Jesse A1 - Buhl, Johannes A1 - Israr, Rameez A1 - Schmidt, Johannes A1 - Bambach, Markus A1 - Fügenschuh, Armin T1 - Mixed-integer programming for additive manufacturing T1 - Gemischt-ganzzahlige Programmierung für die additive Fertigung N2 - Since the beginning of its development in the 1950s, mixed integer programming (MIP) has been used for a variety of practical application problems, such as sequence optimization. Exact solution techniques for MIPs, most prominently branch-and-cut techniques, have the advantage (compared to heuristics such as genetic algorithms) that they can generate solutions with optimality certificates. The novel process of additive manufacturing opens up a further perspective for their use. With the two common techniques, Wire Arc Additive Manufacturing (WAAM) and Laser Powder Bed Fusion (LPBD), the sequence in which a given component geometry must be manufactured can be planned. In particular, the heat transfer within the component must be taken into account here, since excessive temperature gradients can lead to internal stresses and warpage after cooling. In order to integrate the temperature, heat transfer models (heat conduction, heat radiation) are integrated into a sequencing model. This leads to the problem class of MIPDECO: MIPs with partial differential equations (PDEs) as further constraints. We present these model approaches for both manufacturing techniques and carry out test calculations for sample geometries in order to demonstrate the feasibility of the approach. N2 - Die gemischt-ganzzahlige Programmierung (GGP) wurde seit Beginn ihrer Entwicklung in den 1950er Jahren für eine Vielzahl praktischer Anwendungsprobleme, wie beispielsweise die Reihenfolgeoptimierung, eingesetzt. Exakte Lösungstechniken für GGPe, allen voran Verzweige-und-Begrenze-Techniken, haben (im Vergleich zu Heuristiken wie Genetischen Algorithmen) den Vorteil, dass sie Lösungen mit Optimalitätszertifikaten generieren können. Das neuartige Verfahren der Additiven Fertigung eröffnet eine weitere Perspektive für deren Einsatz. Mit den beiden gängigen Verfahren "Additive Fertigung mit Drahtlichtbogen" und "Laser-Pulverbett-Schmelzen" lässt sich die Reihenfolge planen, in der eine vorgegebene Bauteilgeometrie gefertigt werden sollte. Dabei ist insbesondere der Wärmeübergang innerhalb des Bauteils zu berücksichtigen, da zu hohe Temperaturgradienten beim Abkühlen zu Eigenspannungen und Verformungen führen können. Zur Integration der Temperatur werden Wärmeübergangsmodelle (Wärmeleitung, Wärmestrahlung) in ein mathematisches Reihenfolgemodell integriert. Dies führt zur Problemklasse von GGPPDGL: GGPe mit partiellen Differentialgleichungen (PDGLn) als weitere Nebenbedingungen. Wir stellen diese Modellansätze für beide Fertigungstechniken vor und führen Testrechnungen für Probegeometrien durch, um die Machbarkeit des Ansatzes zu demonstrieren. T3 - Cottbus Mathematical Preprints - 23, 2021 KW - Wire arc additive manufacturing KW - Laser powder bed fusion KW - Mixed-integer programming KW - Partial differential equations KW - Finite element method KW - Additive Fertigung mit Drahtlichtbogen KW - Laser-Pulverbett-Schmelzen KW - Gemischt-ganzzahlige Programmierung KW - Partielle Differenzialgleichungen KW - Finite-Elemente-Methode KW - Rapid Prototyping KW - Ganzzahlige Optimierung KW - Finite-Elemente-Methode KW - Partielle Differentialgleichung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-57317 ER - TY - RPRT A1 - Dee, Robin A1 - Fügenschuh, Armin A1 - Kaimakamis, George T1 - The unit re-balancing problem T1 - Das Einheiten-Umverteilungs-Problem N2 - We describe the problem of re-balancing a number of units distributed over a geographic area. Each unit consists of a number of components. A value between 0 and 1 describes the current rating of each component. By a piecewise linear function this value is converted into a nominal status assessment. The lowest of the statuses determines the efficiency of a unit, and the highest status its cost. An unbalanced unit has a gap between these two. To re-balance the units, components can be transferred. The goal is to maximize the efficiency of all units. On a secondary level, the cost for the re-balancing should be minimal. We present a mixed-integer nonlinear programming formulation for this problem, which describes the potential movement of components as a multi-commodity flow. The piecewise linear functions needed to obtain the status values are reformulated using inequalities and binary variables. This results in a mixed-integer linear program, and numerical standard solvers are able to compute proven optimal solutions for instances with up to 100 units. We present numerical solutions for a set of test instances and a bi-criteria objective function, and discuss the trade-off between cost and efficiency. N2 - Wir beschreiben das Problem der Umverteilung einer Anzahl von Einheiten, die über ein geografisches Gebiet verteilt sind. Jede Einheit besteht aus einer Reihe von Komponenten. Ein Wert zwischen 0 und 1 beschreibt die aktuelle Bewertung jeder Komponente. Durch eine stückweise lineare Funktion wird dieser Wert in eine nominale Zustandsbewertung umgerechnet. Der niedrigste Status bestimmt die Effizienz einer Einheit und der höchste Status seine Kosten. Eine unausgeglichene Einheit weist eine Lücke zwischen diesen beiden auf. Um die Einheiten neu auszubalancieren, können Komponenten übertragen werden. Ziel ist es, die Effizienz aller Einheiten zu maximieren. Auf einer untergeordneten Ebene sollten die Kosten für die Umverteilung minimal sein. Für dieses Problem stellen wir eine gemischt-ganzzahlige nichtlineare Modellformulierung vor, die die potenzielle Bewegung von Komponenten als Mehrgüterfluss beschreibt. Die stückweise linearen Funktionen, die zum Erhalten der Statuswerte benötigt werden, werden unter Verwendung von Ungleichungen und binären Variablen umformuliert. Dies führt zu einem gemischt-ganzzahligen linearen Programm, und numerische Standardlöser sind in der Lage, beweisbar optimale Lösungen für Instanzen mit bis zu 100 Einheiten zu berechnen. Wir präsentieren numerische Lösungen für eine Reihe von Testinstanzen und eine bikriterielle Zielfunktion und diskutieren den Kompromiss zwischen Kosten und Effizienz. T3 - Cottbus Mathematical Preprints - 22, 2021 KW - Re-balancing problem KW - Efficiency KW - Mixed-integer linear programming KW - Bi-criteria optimization KW - Umverteilungsproblem KW - Effizienz KW - Gemischt-ganzzahlige Programmierung KW - Bikriterielle Optimierung KW - Ganzzahlige Optimierung KW - Optimierungsproblem KW - Effizienz Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56587 ER - TY - THES A1 - Roman, Anschel Julio ED - Fügenschuh, Armin T1 - Künstliche neuronale Netze in biomedizinischen Anwendungen T1 - Artificial neuronal networks in biomedical applications N2 - Die Bachelorarbeit beschäftigt sich mit der Entwicklung effizienter Methoden für die Klassifizierung der Stadien von Zellen. Hierbei liegt der Fokus auf sogenannten Deep-Learning-Algorithmen. Diese haben sich unter anderem in der Bilderkennung als sehr leistungsfähig erwiesen und können genutzt werden, um große Mengen von mikroskopischen Zellbildern in kurzer Zeit zu klassifizieren. Aufgezeigt werden Möglichkeiten zur Optimierung solcher Algorithmen mit dem Ziel, Genauigkeit und Speichergröße zu verbessern. Es wurden hierbei der Einfluss von verschiedenen Parametern auf die Performance eines Algorithmus untersucht und gegenübergestellt, verschiedene etablierte Modelle miteinander verglichen und eine Auswahl gängiger Methoden zur Modell-Optimierung getestet. Genutzt wurde die Software-Bibliothek TensorFlow, welche über die Programmiersprache Python angesprochen wird. Reale Anwendungsdaten wurden von der Firma Medipan zur Verfügung gestellt. N2 - The bachelor thesis deals with the development of efficient methods for the classification of cell stages. The focus here is on so-called deep learning algorithms. Among other things, these have proven to be very powerful in image recognition and can be used to classify large quantities of microscopic cell images in a short time. Possibilities for optimizing such algorithms with the aim of improving accuracy and memory size are shown. The influence of various parameters on the performance of an algorithm was examined and compared, various established models were compared with one another and a selection of common methods for model optimization were tested. The TensorFlow software library was used, which is addressed via the Python programming language. Real application data were provided by Medipan. T3 - Cottbus Mathematical Preprints - 20, 2021 KW - Künstliche neuronale Netze KW - Tiefes Lernen KW - Nichtlineare Optimierung KW - Bilderkennung KW - Bildklassifizierung KW - Artificial neuronal networks KW - Deep learning KW - Nonlinear optimization KW - Image recognition KW - Image classification KW - Neuronales Netz KW - Mustererkennung KW - Deep learning KW - Nichtlineare Optimierung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56309 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin T1 - Planning inspection flights with an inhomogeneous fleet of micro aerial vehicles T1 - Planung von Inspektionsflügen mit einer inhomogenen Flotte von Kleinstdrohnen N2 - We consider the problem of planning an inspection flight to a given set of waypo- ints using an inhomogeneous fleet of multirotor, battery-driven micro aerial vehicles (MAVs). Therein, two subproblems must be solved. On the one side, the detailed trajectories of all MAVs must be planned, taking technical and environmental restrictions into account and on the other side, the MAVs must be assigned to the waypoints considering their installed equipment. The goal is to visit all waypoints in minimal time. The strong interaction of the two subproblems makes it necessary to tackle them simultaneously. Several aspects are taken into account to allow realistic solutions. A two-level time grid approach is applied to achieve smooth trajectories, while the flight dynamics of the MAVs are modeled in great detail. Safety distances must be maintained between them and they can recharge at charging stations located within the mission area. There can be polyhedral restricted air spaces that must be avoided. Furthermore, weather conditions are incorporated by polyhedral wind zones affecting the drones and each waypoint has a time window within it must be visited. We formulate this problem as a mixed-integer linear program and show whether the state-of-the-art numerical solver Gurobi is applicable to solve model instances. N2 - Wir betrachten das Problem der Planung eines Inspektionsfluges zu einer gegebenen Menge von Wegpunkten unter Verwendung einer inhomogenen Flotte von batteriebetriebenen Mikroluftfahrzeugen (Kleinstdrohnen, MAVs) mit mehreren Rotoren. Dabei müssen zwei Teilprobleme gelöst werden. Einerseits müssen die detaillierten Trajektorien aller MAVs unter Berücksichtigung technischer und umweltbedingter Restriktionen geplant werden und andererseits müssen die MAVs unter Berücksichtigung ihrer installierten Ausrüstung den Wegpunkten zugeordnet werden. Ziel ist es, alle Wegpunkte in kürzester Zeit zu erreichen. Die starke Wechselwirkung der beiden Teilprobleme macht es notwendig, sie gleichzeitig zu betrachten. Mehrere Aspekte werden berücksichtigt, um realistische Lösungen zu ermöglichen. Ein zweistufiger Zeitrasteransatz wird angewendet, um glatte Flugbahnen zu erzielen, während die Flugdynamik der MAVs sehr detailliert modelliert wird. Zwischen ihnen müssen Sicherheitsabstände eingehalten werden und sie können an Ladestationen im Einsatzgebiet aufgeladen werden. Es kann polyedrisch begrenzte Lufträume geben, die umflogen werden müssen. Darüber hinaus werden Wetterbedingungen durch polyedrische Windzonen berücksichtigt, die die Drohnen beeinflussen und jeder Wegpunkt hat ein Zeitfenster, innerhalb dessen er besucht werden muss. Wir formulieren dieses Problem als gemischt-ganzzahliges lineares Programm und zeigen, dass moderne numerische Löser, wie Gurobi, zur Lösung von Modellinstanzen anwendbar sind. T3 - Cottbus Mathematical Preprints - 21, 2021 KW - Mixed integer linear programming KW - Inspection path planning KW - Trajectory planning KW - Micro aerial vehicles KW - Gemischt-ganzzahlige Programmierung KW - Inspektionspfadplanung KW - Trajektorienplanung KW - Kleinstdrohnen KW - Ganzzahlige Optimierung KW - Tourenplanung KW - Drohne Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56569 ER - TY - THES A1 - Flister, Tobias ED - Fügenschuh, Armin T1 - Eine Heuristik zur Lösung ganzzahliger Programme mit quadratischen Nebenbedingungen T1 - A heuristic for the solution of integer programs with quadratic constraints N2 - Die Frage nach dem Lösen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empfänger in einem Ozeanabschnitt so platziert, dass möglichst jeder Bereich durch mindestens ein Sender-Empfänger-Paar überwacht werden kann. Diskretisiert man den Abschnitt räumlich, so kann die Frage nach der Platzierung durch binäre Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Binärvariablen multipliziert, was einem logischen „Und“ entspricht. Um die Modelle halbwegs schnell numerisch zu lösen, wurden in der Literatur zahlreiche Linearisierungstechniken entwickelt und erprobt. Trotz allem Fortschritt ist man weit davon entfernt, Instanzen mit deutlich mehr als 100 Diskretisierungspunkten in annehmbarer Zeit zur Optimalität zu lösen. In dieser Bachelorarbeit werden heuristische Lösungsverfahren entwickelt, welche in der Lage sind, innerhalb kürzester Zeit gute (aber nicht beweisbar optimale) Lösungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empfänger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen präsentiert und mit einem exakten Ansatz verglichen. N2 - The question of solving integer programs with quadratic constraints plays a role when setting up multistatic sonar networks. Sound transmitters and receivers are placed in an ocean section in such a way that, if possible, every area can be monitored by at least one transmitter-receiver pair. If the section is discretized spatially, the question of placement can be described by binary decision variables. Since it depends on the placement in pairs, the binary variables are multiplied in the models, which corresponds to a logical "And". In order to numerically solve the models reasonably quickly, numerous linearization techniques have been developed and tested in the literature. Despite all the progress, one is far from solving instances with significantly more than 100 discretization points in a reasonable time to optimality. In this bachelor thesis, heuristic solution methods are developed, which are able to deliver good (but not provable optimal) solutions within a very short time. The starting point was the basic idea of alternately optimizing the transmitter and receiver until there was no further improvement. Numerical results are presented using test instances and compared with an exact approach. T3 - Cottbus Mathematical Preprints - 19, 2021 KW - Heuristiken KW - Ganzzahlige Programmierung KW - Quadratische Nebenbedingungen KW - Multistatisches Sonar KW - Netzplanung KW - Heuristics KW - Integer programming KW - Quadratic constraints KW - Multi-static sonar KW - Network planning KW - Ganzzahlige Optimierung KW - Heuristik KW - Netzplanung Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-56175 ER - TY - RPRT A1 - Schmidt, Johannes A1 - Buhl, Johannes A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A finite element approach for trajectory optimization in Wire-Arc Additive Manufacturing T1 - Einsatz der Finite-Elemente-Methode zur Pfadoptimierung in Wire-Arc Additive Manufacturing N2 - In wire-arc additive manufacturing (WAAM), the desired workpiece is built layerwise by a moving heat source depositing droplets of molten wire on a substrate plate. To reduce material accumulations, the trajectory of the weld source should be continuous, but transit moves without welding, called deadheading, are possible. The enormous heat of the weld source causes large temperature gradients, leading to a strain distribution in the welded material which can lead even to cracks. In summary, it can be concluded that the temperature gradient reduce the quality of the workpiece. We consider the problem of finding a trajectory of the weld source with minimal temperature deviation from a given target temperature for one layer of a workpiece with welding segments broader than the width of the weld pool. The temperature distribution is modeled using the finite element method. We formulate this problem as a mixed-integer linear programming model and demonstrate its solvability by a standard mixed-integer solver. N2 - Beim Fertigungssprozess des Wire-Arc Additive Manufacturing (WAAM) wird ein Werkstück schichtweise durch eine sich bewegende Wärmequelle aufgebaut, die Tropfen aus geschmolzenem Schweißdraht auf eine Grundplatte aufbringt. Um Materialansammlungen zu reduzieren, sollte die Trajektorie der Schweißquelle zusammenhängend sein, aber Bewegungen ohne Schweißen, Deadheading genannt, sind ebenfalls möglich. Durch die enorme Hitze der Schweißquelle werden große Temperaturunterschiede verursacht, die zu einer Spannungsverteilung im Bauteil führen. Dadurch entsteht Verzug und sogar Risse können auftreten. Deshalb verringern große Temperaturunterschiede die Qualität des Werkstücks. Wir untersuchen das Problem, eine Trajektorie der Schweißquelle mit minimaler Temperaturabweichung von einer gegebenen Zieltemperatur für eine Lage eines Werkstücks mit Schweißsegmenten, die breiter als die Breite des Schweißbads sind, zu finden. Die Temperaturverteilung wird mit Hilfe der Finiten-Elemente-Methode modelliert. Wir formulieren dieses Problem als ein gemischt-ganzzahliges lineares Optimierungsmodell und demonstrieren seine Anwendbarkeit durch einen Standardlöser für gemischt-ganzzahlige Optimierungsprobleme. T3 - Cottbus Mathematical Preprints - 18, 2021 KW - Additive manufacturing KW - Heat equation KW - Path optimization KW - Finite element method KW - Mixed-integer linear programming KW - Additive Fertigung KW - Pfadoptimierung KW - Wärmeleitungsgleichung KW - Finite-Elemente-Methode KW - Gemischt-ganzzahlige lineare Programmierung KW - Rapid Prototyping KW - Wärmeleitungsgleichung KW - Bahnplanung KW - Ganzzahlige lineare Optimierung KW - Finite-Elemente-Methode Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-55753 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 - RPRT A1 - Schmidt, Johannes A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - A two-time-level model for mission and flight planning of an inhomogeneous fleet of unmanned aerial vehicles T1 - Ein Zwei-Zeitraster-Modell für die Missions- und Flugplanung einer inhomogenen Flotte unbemannter Luftfahrzeuge N2 - We consider the mission and flight planning problem for an inhomogeneous fleet of unmanned aerial vehicles (UAVs). Therein, the mission planning problem of assigning targets to a fleet of UAVs and the flight planning problem of finding optimal flight trajectories between a given set of waypoints are combined into one model and solved simultaneously. Thus, trajectories of an inhomogeneous fleet of UAVs have to be specified such that the sum of waypoint-related scores is maximized, considering technical and environmental constraints. Several aspects of an existing basic model are expanded to achieve a more detailed solution. A two-level time grid approach is presented to smooth the computed trajectories. The three-dimensional mission area can contain convex-shaped restricted airspaces and convex subareas where wind affects the flight trajectories. Furthermore, the flight dynamics are related to the mass change, due to fuel consumption, and the operating range of every UAV is altitude-dependent. A class of benchmark instances for collision avoidance is adapted and expanded to fit our model and we prove an upper bound on its objective value. Finally, the presented features and results are tested and discussed on several test instances using GUROBI as a state-of-the-art numerical solver. N2 - Wir betrachten das Missions- und Flugplanungsproblem für eine inhomogene Flotte unbemannter Luftfahrzeuge (UAVs). Darin werden das Missionsplanungsproblem der Zuweisung von Zielen zu einer Flotte von UAVs und das Flugplanungsproblem der Suche nach optimalen Flugbahnen zwischen einer gegebenen Menge von Wegpunkten in einem Modell kombiniert und gelöst. Darin müssen die Flugbahnen einer inhomogenen Flotte von UAVs so spezifiziert werden, dass die Summe der wegpunktbezogenen Bewertungen unter Berücksichtigung technischer und umweltbedingter Einschränkungen maximiert wird. Eine vorhandenes Grundmodell wird erweitert, um eine detailliertere Lösung zu erzielen. Ein zweistufiger Zeitrasteransatz wird vorgestellt, um die berechneten Trajektorien zu glätten. Das dreidimensionale Missionsgebiet kann konvex geformte eingeschränkte Lufträume und konvexe Teilbereiche enthalten, in denen Wind die Flugbahnen beeinflusst. Darüber hinaus hängt die Flugdynamik mit der Massenänderung aufgrund des Kraftstoffverbrauchs zusammen, und die Reichweite jedes UAV ist höhenabhängig. Eine Klasse von Benchmark-Instanzen zur Kollisionsvermeidung wird an unser Modell angepasst und erweitert, und wir beweisen eine Obergrenze für den Zielfunktionswert. Schließlich werden die vorgestellten Funktionen und Ergebnisse an mehreren Testinstanzen getestet und diskutiert, wobei GUROBI als hochmoderner numerischer Löser verwendet wird. T3 - Cottbus Mathematical Preprints - 16, 2021 KW - Mixed-integer nonlinear programming KW - Mission Planning KW - Inhomogeneous Fleet KW - Time Windows KW - Linearization methods KW - Gemischt-ganzzahlige nichtlineare Programming KW - Missionsplanung KW - Inhomogene Flotte KW - Zeitfenster KW - Linearisierungsmethoden KW - Nichtlineare Optimierung KW - Tourenplanung KW - Flugkörper Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54619 ER - TY - THES A1 - Tchouto Mbatchou, Thierry ED - Fügenschuh, Armin T1 - Training of artificial neuronal networks with nonlinear optimization techniques T1 - Training künstlicher Neuronaler Netze mit Techniken der nichtlinearen Optimierung N2 - Machine learning is a field that has been the object of study of many researchers around the globe during the last decades. Very often to solve machine learning challenges like classification problems for example, one needs to train an artificial neural network. To train this network a certain loss function has to be minimized. There is a ubiquitous approach to achieve this which consists of using variants of the stochastic gradient descent combined with the backpropagation algorithm. In our work, we aimed at testing a rather non-conventional scheme consisting of making use of the solvers a software called AMPL offers. N2 - Maschinelles Lernen ist ein Gebiet, mit dem sich in den letzten Jahrzehnten viele Forscher rund um den Globus intensiv auseinandergesetzt haben. Um Probleme im Gebiet des maschinellen Lernens lösen zu können, wie zum Beispiel Klassifizierungsprobleme, muss man sehr oft ein künstliches neuronales Netz trainieren. Damit ein solches Netz erfolgreich trainiert werden kann, muss eine bestimmte Verlustfunktion minimiert werden. Es gibt einen allgegenwärtigen Ansatz, um dies zu erreichen, der darin besteht, Varianten des stochastischen Gradientenabstiegs kombiniert mit dem Backpropagation-Algorithmus zu verwenden. In unserer Arbeit wollten wir ein eher unkonventionelles Schema testen, indem wir die von einer Software names AMPL angebotenen Solver gebrauchen. T3 - Cottbus Mathematical Preprints - 15, 2021 KW - Nonlinear optimization KW - Artificial neuronal networks KW - Image recognition KW - Nichtlineare Optimierung KW - Künstliche Neuronale Netze KW - Bilderkennung KW - Bilderkennung KW - Neuronales Netz KW - Nichtlineare Optimierung KW - AMPL Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-54042 ER - TY - THES A1 - Zazai, M. Fawad ED - Fügenschuh, Armin T1 - Berechnung der Trajektorien für die Entwicklung von optimalen Routen T1 - Computing the trajectories for the development of optimal routes N2 - Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gelände wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalität garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien für die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repräsentiert die Topographie eines Geländes. U wird näherungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die kürzesten Wege für den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler Länge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten Höhenvariationen oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien gebildet, um dieses Problem zu einem multikriteriellen Optimierungsproblem zu erweitern. Ein Algorithmus für den kürzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse für die Konstruktion neuer Routen zu berechnen. N2 - Planning the construction of new transit routes or power lines on terrain is usually carried out manually by engineers, with no guarantee of optimality. We introduce a new approach for the computation of optimal trajectories for the development of new transit routes and power lines between two locations on a submanifold U of IR³ representing the topography of a terrain. U is approximatively modeled by a special weighted grid. On this grid, the shortest paths for the construction of new routes are determined, whereby we consider three optimization criteria: routes with minimal length, routes with lowest construction costs, and routes with minimum absolute altitude variations or minimum absolute gradients. Subsequently, a combination of these criteria is used to expand this problem into a multi-criteria optimization problem. A shortest path algorithm, such as the Dijkstra algorithm, is used to compute optimal compromises for the construction of new routes. T3 - Cottbus Mathematical Preprints - 14, 2020 KW - Kürzeste Wege KW - Trajektorienplanung KW - Optimale Routen KW - Multikriterielle Optimierung (Pareto-Front) KW - Geoinformationssysteme KW - Shortest paths KW - Trajectory planning KW - Optimal routes KW - Multi-criteria optimization (Pareto frontier) KW - Geographic information system KW - Bahnplanung KW - Geoinformationssystem KW - Kürzester-Weg-Problem KW - Multikriterielle Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-52286 SN - 2627-6100 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 - RPRT A1 - Ocloo, Valentina E. A1 - Fügenschuh, Armin A1 - Pamen, Olivier M. ED - Fügenschuh, Armin T1 - A new mathematical model for a 3D container packing problem N2 - Wir betrachten das Problem der Einzelcontainerpackung eines Unternehmens, das seine Kunden bedienen muss, indem es zuerst die Produkte in Kartons legt und diese dann in einen Container lädt. Für dieses Problem entwickeln und lösen wir ein lineares gemischt-ganzzahliges Modell. Unser Modell berücksichtigt geometrische Randbedingungen, beispielsweise Überlappungsverbote, Orientierungs-Bedingungen und Randbedingungen für die relative Positionierung der Kartons. Wir betrachten auch die Erweiterung des Modells durch die Integration der Schwerpunktsabweichung der Packung vom Containermittelpunkt. Das Modell wurde an einer großen Anzahl von realen Instanzen getestet, die bis zu 41 Kartons enthalten. In den meisten Fällen wurden optimale Lösungen erzielt bzw. nah-optimale Lösungen mit beweisbar kleiner Optimalitätslücke. N2 - We address the single container packing problem of a company that has to serve its customers by first placing the products in boxes and then loading the boxes into a container. We approach the problem by developing and solving mixed-integer linear models. Our models consider geometric constraints that feature non-overlapping constraints, box orientation constraints, dimensionality constraints, relative packing position constraints, and linearity constraints. We also develop an extension of the models by integrating load balance and the deviation of the center of gravity. We tested the models on a broad set of real instances involving up to 41 boxes and obtained optimal solutions in most cases and very small gaps when optimality could not be proven. T3 - Cottbus Mathematical Preprints - 12, 2020 KW - Container packing problem KW - Mixed-integer programming KW - Box orientation KW - Non-overlapping KW - Center of gravity deviation KW - Optimierungsproblem KW - Container KW - Lineare Optimierung KW - Logistik Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50880 SN - 2627-6100 ER - TY - RPRT A1 - Johannsmann, Leonie M. A1 - Craparo, Emily M. A1 - Dieken, Thor L. A1 - Fügenschuh, Armin A1 - Seitner, Björn O. ED - Fügenschuh, Armin T1 - Stochastic mixed-integer programming for a spare parts inventory management problem N2 - The German Armed Forces provide an operation contingent to support the North Atlantic Treaty Organization (NATO) Response Force (NRF). For this purpose, a „warehouse” containing accommodations, food supplies, medical supplies, and spare parts for the systems has to be available. Such a warehouse is restricted in weight, in order to be quickly movable in an upcoming deployment situation. It should be able to supply the NRF troops for a certain amount of time (e.g., one month) without re-supply from the outside. To ensure optimal use of such a restricted warehouse, we developed the computer program „The OPtimization of a Spare Parts Inventory” (TOPSPIN) to find an optimal mix of spare parts to restore a set of systems to functionality. Each system is composed of several parts, and it can only be used again in the mission if all broken parts are replaced. The failure rate of the individual parts follows a given random distribution, and during deployment it is expected to be higher than in the homeland. Due to the stochastic nature of the problem, we generate scenarios that simulate the actual failure of the parts. The backbone of TOPSPIN is a mixed-integer linear program that determines an optimal, scenario-robust mix of spare parts and is solved using standard state-of-the-art numerical solvers. Using input data provided by the Logistikzentrum, we analyze how many scenarios need to be generated in order to determine reliable solutions. Moreover, we analyze the composition of the warehouse over a variety of different weight restrictions, and we calculate the number of repairable systems as a function of this bound. N2 - Die Bundeswehr stellt ein Einsatzkontingent zur Unterstützung der NATO Response Force (NRF) zur Verfügung. Zu diesem Zweck muss ein Lager mit Unterkünften, Lebensmitteln, medizinischer Versorgung und Ersatzteilen für die Systeme vorhanden sein. Ein solches Lager ist gewichtsbeschränkt, um in einer bevorstehenden Einsatzsituation schnell versendbar zu sein. Es sollte in der Lage sein, die NRF-Truppen für eine bestimmte Zeitspanne (z. B. einen Monat) zu versorgen, ohne von außen erneut zu versorgt zu werden. Um eine optimale Nutzung eines solchen eingeschränkten Lagers zu gewährleisten, haben wir das Computerprogramm „The OPtimization of a Spare Parts INventory" (TOPSPIN) entwickelt, um eine optimale Mischung von Ersatzteilen zu finden, mit der die Funktionalität einer Reihe von Systemen wiederhergestellt werden kann. Jedes System besteht aus mehreren Teilen und kann nur dann in der Mission wieder verwendet werden, wenn alle defekten Teile ersetzt wurden. Die Ausfallrate der einzelnen Teile richtet sich nach einer vorgegebenen Zufallsverteilung und wird im Einsatz voraussichtlich höher sein als im Heimatland. Aufgrund der stochastischen Natur des Problems generieren wir Szenarien, die den tatsächlichen Ausfall der Teile simulieren. Das Grundgerüst von TOPSPIN ist ein lineares gemischt-ganzzahliges Programm, das einen optimalen, Szenario-stabilen Ersatzteilmix ermittelt und mit den modernen numerischen Standardverfahren gelöst wird. Anhand der vom Logistikzentrum der Bundeswehr bereitgestellten Eingangsdaten analysieren wir, wie viele Szenarien generiert werden müssen, um verlässliche Lösungen zu ermitteln. Darüber hinaus analysieren wir die Zusammensetzung des Lagers über verschiedene Gewichtsbeschränkungen und berechnen die Anzahl der reparierbaren Systeme in Abhängigkeit von dieser Grenze. T3 - Cottbus Mathematical Preprints - 11, 2020 KW - Logisitcs KW - Scenario generation KW - Bestandsmanagement KW - Logistik KW - Ganzzahlige Optimierung KW - Stochastische Optimierung KW - Operations Research KW - Uncertainty KW - Warehouse management KW - Operations research KW - Two-stage stochastic optimization KW - Mixed-integer programming KW - Logistik KW - Szenario-Erzeugung KW - Unsicherheit KW - Lagermanagement KW - Gemischt-ganzzahlige Optimierung KW - Unternehmensforschung KW - Zweistufige stochastische Optimierung Y1 - 2020 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50802 SN - 2627-6100 ER - TY - RPRT A1 - Bähr, Martin A1 - Buhl, Johannes A1 - Radow, Georg A1 - Schmidt, Johannes A1 - Bambach, Markus A1 - Breuß, Michael A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing N2 - We consider two mathematical problems that are connected and occur in the layer-wise production process of a workpiece using Wire-Arc Additive Manufacturing. As the first task, we consider the automatic construction of a honeycomb structure, given the boundary of a shape of interest. In doing this we employ Lloyd’s algorithm in two different realizations. For computing the incorporated Voronoi tesselation we consider the use of a Delaunay triangulation or alternatively, the eikonal equation. We compare and modify these approaches with the aim of combining their respective advantages. Then in the second task, to find an optimal tool path guaranteeing minimal production time and high quality of the workpiece, a mixed-integer linear programming problem is derived. The model takes thermal conduction and radiation during the process into account and aims to minimize temperature gradients inside the material. Its solvability for standard mixed-integer solvers is demonstrated on several test-instances. The results are compared with manufactured workpieces. N2 - Wir betrachten zwei verbundene mathematische Probleme, welche bei der schichtweisen Herstellung eines Werkstücks mittels des Lichtbogendraht-Auftragschweißen, einem additiven Fertigungsverfahren, auftreten. Als erste Aufgabe betrachten wir die automatische Konstruktion einer Wabenstruktur unter Berücksichtigung des Randes einer gewünschten Form. Dabei setzen wir Lloyds Algorithmus in zwei verschiedenen Varianten ein. Zur Berechnung der einbezogenen Voronoi-Parkettierung betrachten wir die Verwendung einer Delaunay-Triangulation und alternativ dazu der Eikonal-Gleichung. Wir vergleichen und modifizieren diese Ansätze mit dem Ziel, ihre jeweiligen Vorteile zu kombinieren. In der zweiten Aufgabe wird dann, um einen optimalen Weg für das Werkzeug zu finden, der eine minimale Produktionszeit zusammen mit einer hohen Qualität des Werkstücks garantiert, ein gemischt-ganzzahliges lineares Programm (MILP) hergeleitet. Das Modell berücksichtigt Wärmeleitung und Strahlung während des Prozesses und zielt darauf ab, Temperaturgradienten innerhalb des Materials zu minimieren. Die Lösbarkeit für Standard-MILP-Löser wird in mehreren Testfällen demonstriert. Die Ergebnisse werden mit real gefertigten Werkstücken verglichen. T3 - Cottbus Mathematical Preprints - 10, 2019 KW - Eikonal equation KW - Centroidal Voronoi tessellation KW - Additive manufacturing KW - Heat transmission KW - Mixed-integer linear programming KW - Geometric optimization KW - Additive Fertigung KW - Gemischt-ganzzahlige Programmierung KW - Geometrische Optimierung KW - Eikonal-Gleichung KW - Zentrierte Voronoi-Parkettierung KW - Wärmeleitung KW - Rapid Prototyping KW - Eikonal KW - Ganzzahlige Optimierung KW - Geometrische Optimierung KW - Wärmeleitung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50796 SN - 2627-6100 ER - TY - RPRT A1 - Zazai, M. Fawad A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Computing the trajectories for the development of optimal routes T1 - Berechnung von Trajektorien für die Entwicklung optimaler Routen N2 - Planning the construction of new transport routes or power lines on terrain is usually carried out manually by engineers, with no guarantee of optimality. We introduce a new approach for the computation of an optimal trajectory for the construction of new transit routes and power lines between two locations on a submanifold U _ R3 representing the topography of a terrain. U is approximatively modeled by a special weighted grid. On this grid, the shortest paths for the construction of new routes are determined, whereby we consider three optimization criteria: routes with minimum distance, routes with lowest construction costs and routes with minimum absolute altitude variations or minimum absolute gradients. Subsequently, a combination of these criteria is used to expand this problem into a multi-criteria optimization problem. A shortest path algorithm, such as the Dijkstra algorithm, is used to compute optimal compromises for the construction of new routes. N2 - Die Planung des Baus neuer Transportwege oder Stromleitungen im Gelände erfolgt in der Regel manuell durch Ingenieure, ohne Nachweis für deren Optimalität. Wir stellen einen neuen Ansatz für die Berechnung einer optimalen Trajektorie für den Bau neuer Transitrouten und Stromleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U des dreidimensionalen Raums vor, welche die Topographie eines Geländes darstellt. U wird durch einen speziell gewichtetes Gittergraphen näherungsweise modelliert. In diesem Graph werden die kürzesten Wege für den Bau neuer Strecken ermittelt, wobei drei Optimierungskriterien berücksichtigt werden: Strecken mit minimaler Entfernung, Strecken mit geringsten Baukosten und Strecken mit minimalen absoluten Höhenunterschieden oder minimalen absoluten Steigungen. Anschließend wird eine Kombination dieser Kriterien verwendet, um dieses Problem zu einem Optimierungsproblem mit mehreren Kriterien zu erweitern. Ein Kürzeste-Wege-Algorithmus, wie das Dijkstra-Verfahren, wird verwendet, um optimale Kompromisse für die Erstellung neuer Routen zu berechnen. T3 - Cottbus Mathematical Preprints - 9, 2019 KW - Shortest path KW - Graph construction KW - Multi-criteria optimization (Pareto frontier) KW - Trajectory planning KW - Topography KW - Kürzeste Wege KW - Graphen-Aufbau KW - Geographische Informationssysteme (GIS) KW - Mehrzieloptimierung (Pareto-Front) KW - Trajektorienplanung KW - Geoinformationssystem KW - Kürzester-Weg-Problem KW - Bahnplanung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50651 SN - 2627-6100 ER - 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 - THES A1 - Blümel, Christian ED - Fügenschuh, Armin T1 - Verfahren für die Berechnung und Abschätzung der Tourenlänge des Handlungsreisendenproblems mit wenigen Orten N2 - Eines der am intensivsten untersuchten Probleme aus dem Bereich der Optimierung stellt das sogenannte Traveling Salesman Problem (TSP, in deutsch: Handlungsreisendenproblem) dar. Die Aufgabe hinter dem Handlungsreisendenproblem besteht darin, für eine gegebene Anzahl an Orten eine Route zu entwickeln, sodass die Gesamtlänge der Route minimal ist. Zudem darf kein Ort, bis auf den ersten, mehrmals besucht werden. Ziel der vorliegenden Bachelorarbeit ist es, statistische Untersuchungen bezüglich der Tourlänge des TSP in Abhängig der Anzahl der besuchten Städte vorzunehmen, wobei der Fokus auf einer kleinen Anzahl von Städten liegt. Dazu wurde das Problem einerseits numerisch gelöst und die Verteilung der Lösungen analysiert. Für Teilaspekte wurden analytische Lösungen berechnet. N2 - One of the most intensively studied problems in the area of optimization is the so-called Traveling Salesman Problem (TSP). The task behind the traveling salesman problem is to develop a route for a given number of locations so that the total length of the Route is minimal. Also, no place, except the first one, can be visited several times. The present bachelor thesis aims to carry out statistical investigations regarding the tour length of the TSP in dependence on the number of visited cities, whereby the focus is on a small number of cities. On the one hand, the problem was solved numerically and the distribution of the solutions was analyzed. For some subproblems, analytic solutions were calculated. T3 - Cottbus Mathematical Preprints - 7, 2019 KW - Handlungsreisendenproblem KW - Gemischt-ganzzahlige lineare Optimierung KW - Modellierung KW - Statistik KW - Verteilungsfunktion KW - Distribution function KW - Traveling Salesman Problem KW - Statistics KW - Mixed-integer linear optimization KW - Modeling KW - Ganzzahlige lineare Optimierung KW - Travelling-salesman-Problem KW - Mathematische Modellierung KW - Verteilungsfunktion Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-50291 SN - 2627-6100 ER - TY - RPRT A1 - Fügenschuh, Armin A1 - Müllenstedt, Daniel A1 - Schmidt, Johannes ED - Fügenschuh, Armin T1 - Mission planning for unmanned aerial vehicles N2 - We formulate the mission planning problem for a meet of unmanned aerial vehicles (UAVs) as a mixed-integer nonlinear programming problem (MINLP). The problem asks for a selection of targets from a list to the UAVs, and trajectories that visit the chosen targets. To be feasible, a trajectory must pass each target at a desired maximal distance and within a certain time window, obstacles or regions of high risk must be avoided, and the fuel limitations must be obeyed. An optimal trajectory maximizes the sum of values of all targets that can be visited, and as a secondary goal, conducts the mission in the shortest possible time. In order to obtain numerical solutions to this model, we approximate the MINLP by a mixed-integer linear program (MILP), and apply a state-of-the-art solver (GUROBI) to the latter on a set of test instances. N2 - Das Missionsplanungsproblem für eine Flotte unbemannter Luftfahrzeuge (UAVs) formulieren wir als nichtlineares gemischt-ganzzahliges Optimierungsproblem (MINLP). Das Problem erfordert eine Auswahl von Zielen aus einer Liste von gegebenen UAVs und deren Flugbahnen, welche die ausgewählten Ziele besuchen. Um zulässig zu sein, muss eine Flugbahn jedes Ziel in einer vorgegebenen maximalen Entfernung und innerhalb eines bestimmten Zeitfensters passieren. Ferner müssen Hindernisse oder Bereiche mit hohem Risiko vermieden werden, und die Kraftstoffbeschränkungen müssen berücksichtigt werden. Eine optimale Mission maximiert die Summe der Werte aller Ziele, die besucht werden können, und führt als sekundäres Ziel die Mission in kürzester Zeit aus. Um numerische Lösungen für dieses Modell zu erhalten, approximieren wir das MINLP durch ein gemischt-ganzzahliges lineares Programm (MILP) und wenden auf Testinstanzen einen numerischen Löser (GUROBI) an. T3 - Cottbus Mathematical Preprints - 6, 2019 KW - Mixed-integer nonlinear programming KW - Trajectory planning KW - Unmanned aerial vehicles KW - Linear approximation KW - Flugkörper KW - Tourenplanung KW - Optimierung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48285 SN - 2627-6100 ER - TY - RPRT A1 - Auer, Peter A1 - Dósa, György A1 - Dulai, Tibor A1 - Fügenschuh, Armin A1 - Näser, Peggy A1 - Ortner, Ronald A1 - Werner-Stark, Ágnes ED - Fügenschuh, Armin T1 - A new heuristic and an exact approach for a production planning problem N2 - We deal with a very complex and hard scheduling problem. Several types of products are processed by a heterogeneous resource set, where resources have different operating capabilities and setup times are considered. The processing of the products follows different workflows, allowing also assembly lines. The goal is to process all products in minimum time, i.e., the makespan is to be minimized. Because of the complexity of the problem an exact solver would require too much running time. We propose a compound method where a heuristic is combined with an exact solver. Our proposed heuristic is composed of several phases applying different smart strategies. In order to reduce the computational complexity of the exact approach, we exploit the makespan determined by the heuristic as an upper bound for the time horizon, which has a direct in uence on the instance size used in the exact approach. We demonstrate the efficiency of our combined method on multiple problem classes. With the help of the heuristic the exact solver is able to obtain an optimal solution in a much shorter amount of time. N2 - Wir betrachten das folgende Planungsproblem: Verschiedene Arten von Produkten werden auf einer Menge von heterogenen Maschinen erstellt, welche unterschiedliche Betriebsarten und Umrüstzeiten haben. Die Verarbeitung der Produkte erfolgt nach unterschiedlichen Arbeitsablaufplänen, da die einzelnen Produkttypen unterschiedliche Fertigungsschritte erfordern. Das Ziel ist es, alle Produkte in minimaler Zeit herzustellen. Aufgrund der Komplexität des Problems benötigen exakte Lösungsverfahren eine recht hohe Rechenzeit. Wir schlagen eine zusammengesetzte Methode vor, bei dem eine Heuristik und ein exakter Löser kombiniert werden. Unsere vorgeschlagene Heuristik besteht aus mehreren Phasen, in denen verschiedene intelligente Strategien angewendet werden. Um die rechnerische Komplexität des exakten Ansatzes zu reduzieren, nutzen wir die durch die Heuristik bestimmte Fertigungsdauer als obere Grenze für den Zeithorizont, was einen direkten Einfluss auf die Instanzgröße des exakten Ansatzes hat. Wir demonstrieren die Effizienz unserer kombinierten Methode an einer großen Menge von Testinstanzen. Mit Hilfe der Heuristik ist der exakte Löser in der Lage, in deutlich kürzerer Zeit eine beweisbar-optimale Lösung zu bestimmen. T3 - Cottbus Mathematical Preprints - 5, 2019 KW - Production planning KW - Mixed-integer programming KW - Heuristics KW - Simulation KW - Fertigungsprogrammplanung KW - Heuristik KW - Optimierung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48278 SN - 2627-6100 ER - TY - RPRT A1 - Stieber, Anke A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - Dealing with time in the multiple traveling salesmen problem with moving targets N2 - The multiple traveling salesmen problem with moving targets is a generalization of the classical traveling salesmen problem, where the targets (cities or objects) are moving over time. Additionally, for each target a visibility time window is given. The task is to find routes for several salesmen so that each target is reached exactly once within its visibility time window and the sum of all traveled distances of all salesmen is minimal. We present different modeling formulations for this TSP variant. The time requirements are modeled differently in each approach. Our goal is to examine what formulation is most suitable in terms of runtime to solve the multiple traveling salesmen problem with moving targets with exact methods. Computational experiments are carried out on randomly generated test instances to compare the different modeling approaches. The results for large-scale instances show, that the best way to model time requirements is to directly insert them into a formulation with discrete time steps. N2 - Das Problem des multiplen Handlungsreisenden mit bewegten Zielen ist eine Verallgemeinerung des Problems des klassischen Handlungsreisenden (TSP), bei dem sich die Ziele (Städte oder Objekte) im Laufe der Zeit bewegen. Zusätzlich wird für jedes Ziel ein Sichtbarkeitszeitfenster angegeben. Die Aufgabe besteht darin, Routen für mehrere Handlungsreisende zu finden, so dass jedes Ziel innerhalb seines Sichtbarkeitszeitfensters genau einmal erreicht wird und die Summe aller zurückgelegten Entfernungen aller Handlungsreisenden minimal ist. Wir präsentieren verschiedene Modellformulierungen für diese TSP-Variante. Die Zeitrestriktionen werden in jedem Ansatz unterschiedlich modelliert. Unser Ziel ist es zu untersuchen, welche Formulierung in Bezug auf die Laufzeit am besten geeignet ist, um das Problem mit mehreren Handlungsreisenden mit bewegten Zielen mit exakten Methoden, welche globale Optimalität garantieren, zu lösen. Computerversuche werden an zufällig generierten Testinstanzen durchgeführt, um die verschiedenen Modellierungsansätze zu vergleichen. Die Ergebnisse für umfangreiche Instanzen zeigen, dass der beste Weg, um Zeitanforderungen zu modellieren, darin besteht, sie in diskreten Zeitschritten direkt in die Formulierung einzufügen. T3 - Cottbus Mathematical Preprints - 4, 2019 KW - Dynamic traveling salesmen problem KW - Moving targets KW - Time-relaxation KW - Integer linear programming KW - Second-order cone programming KW - Travelling-salesman-Problem Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48245 SN - 2627-6100 ER - TY - RPRT A1 - Gnegel, Fabian A1 - Fügenschuh, Armin ED - Fügenschuh, Armin T1 - An iterative graph expansion approach for the scheduling and routing of airplanes N2 - A tourism company that offers fly-in safaris is faced with the challenge to route and schedule its fleet of airplanes in an optimal way. Over the course of a given time horizon several groups of tourists have to be picked up at airports and flown to their destinations within a certain time-window. Furthermore the number of available seats, the consumption of fuel, the maximal takeoff weight, and restrictions on the detour of the individual groups have to be taken into account. The task of optimally scheduling the airplanes and tour groups belongs to the class of vehicle routing problems with pickup and delivery and time-windows. A flow-over-flow formulation on the time expanded graph of the airports was used in the literature in order to model this problem as a mixed integer linear program. Most of the benchmark problems however could not be solved within a time limit of three hours, which was overcome by formulating the problem for a simplified (time-free) graph and the use of an incumbent callback to check for feasibility in the original graph. While this approach led to very good results for instances, where few time-free solutions were infeasible for the original problem, some instances remained unsolved. In order to overcome this problem we derive two new exact formulations that include time as variables. Although these formulations by themselves are not better than the approach from the literature, they allow for an effective construction of graphs which can be interpreted as intermediate graphs between the graph of airports and the expanded graph with vertices for each visit. Using similar relaxation techniques to the time-free approach and constructing these graphs based on solutions of the relaxations guarantees that only critical airports are expanded. A computational study was performed in order to compare the new formulations to the methods from the literature. Within a time limit of 3 hours the new approach was able to find proven optimal solutions for all previously unsolved benchmark instances. Furthermore the average computation time of all benchmark instances was reduced by 90 percent. N2 - Ein Reiseunternehmen, das Fly-in Safaris anbietet, stellt sich die Aufgabe, seine Flottenrouten und deren Zeitplanung optimal zu gestalten. In einem feststehenden Zeitraum müssen mehrere Touristengruppen unter Einhaltung von Fristen von ihrem aktuellen Aufenthaltsort per Flugzeug abgeholt und zu ihrem nächsten Zielflughafen geflogen werden. Weiterhin muss Rücksicht auf die beschränkte Anzahl von Sitzen, den Treibstoffverbrauch, das maximale Startgewicht und Bedingungen an die Umwege der einzelnen Gruppen genommen werden. Die Aufgabe, die Routen der Flugzeuge festzulegen und zeitlich zu planen, gehört zur Problemklasse der Vehicle Routing Probleme mit Pickup und Delivery und Zeitfenstern. Eine Flow-over-Flow Formulierung auf dem zeitexpandierten Graphen der Flughäfen wurde in der Literatur benutzt, um dieses Problem als gemischt-ganzzahliges lineares Programm zu formulieren. Allerdings konnten die meisten Benchmarkprobleme nicht innerhalb von einem Zeitlimit von drei Stunden gelöst werden, was dadurch behoben wurde, dass das Problem für einen vereinfachten (zeitfreien) Graphen formuliert und ein Incumbent Callback zum Überprüfen der Zulässigkeit für den ursprünglichen Graphen implementiert wurde. Während dieser Ansatz sehr gute Resultate für Probleminstanzen lieferte, bei denen nur wenige zeitfreie Lösungen für das ursprüngliche Problem unzulässig waren, blieben einige Instanzen ungelöst. Um dies zu verbessern, leiten wir zwei neue exakte Formulierungen her, die den Aspekt der Zeit als Variablen beinhalten. Obwohl diese Formulierungen für sich genommen nicht besser sind als der zeitfreie Ansatz aus der Literatur, erlauben sie eine effektive Konstruktion von Graphen, die als Zwischenstufen vom Graphen der Flughäfen und dem expandierten Graphen mit Knoten für jede Ankunft angesehen werden können. Die Benutzung von ähnlichen Relaxationstechniken wie im zeitfreien Ansatz und das Aufbauen dieser Graphen anhand von Lösungen der Relaxierungen garantiert, dass nur kritische Knoten expandiert werden. Eine Rechenstudie wurde durchgeführt, um die neuen Formulierungen mit den Methoden aus der Literatur zu vergleichen. Innerhalb eines Zeitlimits von drei Stunden war der neue Ansatz in der Lage, alle vorher ungelösten Benchmarkproblem bis zur beweisbaren Optimalität zu lösen. Außerdem wurde die durchschnittliche Rechenzeit um 90 Prozent reduziert. T3 - Cottbus Mathematical Preprints - 3, 2019 KW - Mixed Integer Linear Programming KW - Operational Research KW - Vehicle Routing Problem KW - Time-Dependent Airplane Routing KW - Dynamic Graph Expansion KW - Routing KW - Mehrdepotproblem KW - Expandierender Graph Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48069 SN - 2627-6100 ER - TY - THES A1 - Werger, Tabea ED - Fügenschuh, Armin T1 - Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr N2 - Die Bachelorarbeit beschäftigt sich mit der Erstellung eines möglichst guten, zulässigen Stundenplans für eine Unteroffiziersschule der Bundeswehr. Die Bildungseinrichtung kann vorhandene Optimierungsprogramme für Stundenpläne nur teilweise zu Rate ziehen, da hier im Vergleich zu normalen Schulen und Universitäten die Veranstaltungen nicht in einem Wochenzyklus stattfinden. Des Weiteren gibt es Spezialveranstaltungen, die nur an bestimmten Tagen besucht werden können. Zusätzlich haben die zu absolvierenden Kurse eine fest vorgegebene Reihenfolge, die beachtet werden muss. T3 - Cottbus Mathematical Preprints - 2, 2019 KW - Mixed-integer programming KW - Operational research KW - School time table planning KW - Ganzzahlige Optimierung KW - Stundenplanerstellung Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48036 SN - 2627-6100 ER - TY - THES A1 - Meier, Yvonne ED - Fügenschuh, Armin T1 - Ein gemischt-ganzzahliger Ansatz zur gleichmäßigen Verkehrsauslastung eines Ballungsraums mittels Verschiebung der Schulanfangszeiten N2 - Die vorliegende Arbeit beschäftigt sich mit der gleichmäßigen Auslastung eines Ballungsraums durch die Verschiebung der Schulanfangszeiten. Ein solcher Ballungsraum entsteht immer dann, wenn sich viele Menschen gleichzeitig, meist nah beeinander, innerhalb eines Sytems bewegen. Insbesondere entsteht ein solcher Ballungsraum bei einem sogenannten Schülertransportproblem, d.h. der Aufgabe, Schüler innerhalb eines Systems zu einer bestimmten Zeit zu ihrer Schule zu transportieren. Die Staffelung der Schulanfangszeiten bietet eine Möglichkeit, dieses hohe Personenaufkommen gezielt zu kontrollieren und zu optimieren. Die gleichmäßigere Auslastung eines Systems beeinflusst auch die Belastung im öffentlichen Nahverkehr. Im Gegensatz zur Schaffung neuer Alternativen können so die vorhandenen Kapazitäten effizienter eingesetzt werden, ohne das Angebot zu reduzieren. Durch das geringere punktuelle Aufkommen von Fahrgästen kann der zur Verfügung stehende Fuhrpark wirksamer genutzt werden. Zusätzlich machen die zu den Stoßzeiten entlasteten Busse und Bahnen den öffentlichen Personennahverkehr für andere Zielgruppen attraktiver. Im Rahmen dieser Arbeit wurde ein gemischt-ganzzahliger Ansatz zur Realisation dieser Aufgabe entwickelt. In Kapitel 1 wird zunächst ein Überblick über verschiedene Betrachtungsweisen und Modelle für Schülertransporte und der Optimierung von Personenaufkommen gegeben, Kapitel 2 widmet sich den notwendigen mathematischen Grundlagen, die für den Ansatz wichtig sind. Im Anschluss werden die Modelle konzipiert und erläutert. Die Ergebnisse werden dargestellt und analysiert, worauf abschließend ein Ausblick über die behandelte Problematik folgt. T3 - Cottbus Mathematical Preprints - 1, 2019 KW - Mixed-Integer Programming KW - Operational Research KW - School Bell Scheduling KW - Optimization of Public Transportation KW - Gemischt-ganzzahlige Optimierung KW - Verkehrsplanung KW - Schülertransport Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:co1-opus4-48023 SN - 2627-6100 ER -