@masterthesis{Bluemel2019, type = {Bachelor Thesis}, author = {Bl{\"u}mel, Christian}, title = {Verfahren f{\"u}r die Berechnung und Absch{\"a}tzung der Tourenl{\"a}nge des Handlungsreisendenproblems mit wenigen Orten}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5029}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50291}, school = {BTU Cottbus - Senftenberg}, year = {2019}, abstract = {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{\"u}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{\"u}glich der Tourl{\"a}nge des TSP in Abh{\"a}ngig der Anzahl der besuchten St{\"a}dte vorzunehmen, wobei der Fokus auf einer kleinen Anzahl von St{\"a}dten liegt. Dazu wurde das Problem einerseits numerisch gel{\"o}st und die Verteilung der L{\"o}sungen analysiert. F{\"u}r Teilaspekte wurden analytische L{\"o}sungen berechnet.}, subject = {Handlungsreisendenproblem; Gemischt-ganzzahlige lineare Optimierung; Modellierung; Statistik; Verteilungsfunktion; Distribution function; Traveling Salesman Problem; Statistics; Mixed-integer linear optimization; Modeling; Ganzzahlige lineare Optimierung; Travelling-salesman-Problem; Mathematische Modellierung; Verteilungsfunktion}, language = {de} } @techreport{SchmidtFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {Planning inspection flights with an inhomogeneous fleet of micro aerial vehicles}, doi = {10.26127/BTUOpen-5656}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56569}, year = {2021}, abstract = {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.}, subject = {Mixed integer linear programming; Inspection path planning; Trajectory planning; Micro aerial vehicles; Gemischt-ganzzahlige Programmierung; Inspektionspfadplanung; Trajektorienplanung; Kleinstdrohnen; Ganzzahlige Optimierung; Tourenplanung; Drohne }, language = {en} } @misc{Werger2021, type = {Master Thesis}, author = {Werger, Tabea}, title = {Instandhaltungsprogramm - NH90 : ein ganzzahliger Ansatz zur Optimierung des Instandhaltungsprogramms eines milit{\"a}rischen Luftfahrzeugs}, doi = {10.26127/BTUOpen-5872}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-58724}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {Die vorliegende Arbeit untersucht die Instandhaltungsplanung eines milit{\"a}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{\"a}ß 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{\"u}r wird ein multikriterielles, ganzzahliges Optimierungsmodell entwickelt. Zum L{\"o}sen wird der Solver IBM ILOG CPLEX Optimization Studio (V 20.1.0.0) verwendet. In der Auswertung wird zus{\"a}tzlich zu den Ergebnissen der Optimierung die Auswirkung von aggregierten und disaggregierten Formulierungen untersucht sowie der Effekt von Ver{\"a}nderungen der Aggressivit{\"a}t von Schnittebenenverfahren.}, subject = {Gemischt-ganzzahlige Optimierung; Hubschrauber; Instandhaltung; Planung; Schnittebenenverfahren; Mixed-integer optimization; Helicopter; Maintenance; Planning; Cutting plane method; Gemischt-ganzzahlige Optimierung; Schnittebenenverfahren; Instandhaltungsplanung}, language = {de} } @phdthesis{Zazai2020, author = {Zazai, M. Fawad}, title = {Berechnung der Trajektorien f{\"u}r die Entwicklung von optimalen Routen}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5228}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-52286}, school = {BTU Cottbus - Senftenberg}, year = {2020}, abstract = {Die Konstruktionsplanung von neuen Transitrouten oder Energieleitungen auf einem topografischen Gel{\"a}nde wird von Ingenieuren in der Regel manuell vorgenommen, ohne dass eine Optimalit{\"a}t garantiert werden kann. Wir stellen einen neuen Ansatz zur Berechnung von Trajektorien f{\"u}r die Entwicklung neuer optimaler Transitrouten und Energieleitungen zwischen zwei Standorten auf einer Untermannigfaltigkeit U von IR³ vor. Diese Untermannigfaltigkeit repr{\"a}sentiert die Topographie eines Gel{\"a}ndes. U wird n{\"a}herungsweise durch ein spezielles gewichtetes Gitternetz modelliert. Auf diesem Gitternetz werden die k{\"u}rzesten Wege f{\"u}r den Bau neuer Routen bestimmt, wobei wir drei Optimierungskriterien betrachten werden: Routen mit minimaler L{\"a}nge, Routen mit geringsten Baukosten und Routen mit minimalen absoluten H{\"o}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{\"u}r den k{\"u}rzesten Weg, wie der Dijkstra-Algorithmus, wird verwendet, um optimale Kompromisse f{\"u}r die Konstruktion neuer Routen zu berechnen.}, subject = {K{\"u}rzeste Wege; Trajektorienplanung; Optimale Routen; Multikriterielle Optimierung (Pareto-Front); Geoinformationssysteme; Shortest paths; Trajectory planning; Optimal routes; Multi-criteria optimization (Pareto frontier); Geographic information system; Bahnplanung; Geoinformationssystem; K{\"u}rzester-Weg-Problem; Multikriterielle Optimierung}, language = {de} } @masterthesis{TchoutoMbatchou2021, type = {Bachelor Thesis}, author = {Tchouto Mbatchou, Thierry}, title = {Training of artificial neuronal networks with nonlinear optimization techniques}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5404}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54042}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {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.}, subject = {Nonlinear optimization; Artificial neuronal networks; Image recognition; Nichtlineare Optimierung; K{\"u}nstliche Neuronale Netze; Bilderkennung; Bilderkennung; Neuronales Netz; Nichtlineare Optimierung; AMPL}, language = {en} } @techreport{ZazaiFuegenschuh2019, author = {Zazai, M. Fawad and F{\"u}genschuh, Armin}, title = {Computing the trajectories for the development of optimal routes}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5065}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50651}, year = {2019}, abstract = {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.}, subject = {Shortest path; Graph construction; Multi-criteria optimization (Pareto frontier); Trajectory planning; Topography; K{\"u}rzeste Wege; Graphen-Aufbau; Geographische Informationssysteme (GIS); Mehrzieloptimierung (Pareto-Front); Trajektorienplanung; Geoinformationssystem; K{\"u}rzester-Weg-Problem; Bahnplanung}, language = {en} } @misc{Zell2022, type = {Master Thesis}, author = {Zell, Sascha}, title = {Agentenbasierte Modellierung und Simulation der Rettungskette : eine Fallstudie in der Lausitz}, doi = {10.26127/BTUOpen-5873}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-58731}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {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.}, subject = {Emergency medical service system; Agent-based simulation; Rescue chain; Rettungsdienst; Rettungskette; Agentenbasiertes Simulationsmodell; Cottbus; Rettungswesen; Geoinformationssystem; Simulation}, language = {de} } @techreport{BeisegelBuhlIsraretal.2021, type = {Working Paper}, author = {Beisegel, Jesse and Buhl, Johannes and Israr, Rameez and Schmidt, Johannes and Bambach, Markus and F{\"u}genschuh, Armin}, title = {Mixed-integer programming for additive manufacturing}, doi = {10.26127/BTUOpen-5731}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-57317}, year = {2021}, abstract = {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.}, subject = {Wire arc additive manufacturing; Laser powder bed fusion; Mixed-integer programming; Partial differential equations; Finite element method; Additive Fertigung mit Drahtlichtbogen; Laser-Pulverbett-Schmelzen; Gemischt-ganzzahlige Programmierung; Partielle Differenzialgleichungen; Finite-Elemente-Methode; Rapid Prototyping ; Ganzzahlige Optimierung; Finite-Elemente-Methode; Partielle Differentialgleichung}, language = {en} } @masterthesis{Roman2021, type = {Bachelor Thesis}, author = {Roman, Anschel Julio}, title = {K{\"u}nstliche neuronale Netze in biomedizinischen Anwendungen}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5630}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56309}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {Die Bachelorarbeit besch{\"a}ftigt sich mit der Entwicklung effizienter Methoden f{\"u}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{\"a}hig erwiesen und k{\"o}nnen genutzt werden, um große Mengen von mikroskopischen Zellbildern in kurzer Zeit zu klassifizieren. Aufgezeigt werden M{\"o}glichkeiten zur Optimierung solcher Algorithmen mit dem Ziel, Genauigkeit und Speichergr{\"o}ße zu verbessern. Es wurden hierbei der Einfluss von verschiedenen Parametern auf die Performance eines Algorithmus untersucht und gegen{\"u}bergestellt, verschiedene etablierte Modelle miteinander verglichen und eine Auswahl g{\"a}ngiger Methoden zur Modell-Optimierung getestet. Genutzt wurde die Software-Bibliothek TensorFlow, welche {\"u}ber die Programmiersprache Python angesprochen wird. Reale Anwendungsdaten wurden von der Firma Medipan zur Verf{\"u}gung gestellt.}, subject = {K{\"u}nstliche neuronale Netze; Tiefes Lernen; Nichtlineare Optimierung; Bilderkennung; Bildklassifizierung; Artificial neuronal networks; Deep learning; Nonlinear optimization; Image recognition; Image classification; Neuronales Netz; Mustererkennung; Deep learning; Nichtlineare Optimierung}, language = {de} } @masterthesis{Flister2021, type = {Bachelor Thesis}, author = {Flister, Tobias}, title = {Eine Heuristik zur L{\"o}sung ganzzahliger Programme mit quadratischen Nebenbedingungen}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5617}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56175}, school = {BTU Cottbus - Senftenberg}, year = {2021}, abstract = {Die Frage nach dem L{\"o}sen von ganzzahligen Programmen mit quadratischen Nebenbedingungen spielt beim Aufbau multistatischer Sonar-Netze eine Rolle. Hierbei werden Schall-Sender und -Empf{\"a}nger in einem Ozeanabschnitt so platziert, dass m{\"o}glichst jeder Bereich durch mindestens ein Sender-Empf{\"a}nger-Paar {\"u}berwacht werden kann. Diskretisiert man den Abschnitt r{\"a}umlich, so kann die Frage nach der Platzierung durch bin{\"a}re Entscheidungsvariablen beschrieben werden. Da es auf die paarweise Platzierung ankommt, werden in den Modellen die Bin{\"a}rvariablen multipliziert, was einem logischen „Und" entspricht. Um die Modelle halbwegs schnell numerisch zu l{\"o}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{\"a}t zu l{\"o}sen. In dieser Bachelorarbeit werden heuristische L{\"o}sungsverfahren entwickelt, welche in der Lage sind, innerhalb k{\"u}rzester Zeit gute (aber nicht beweisbar optimale) L{\"o}sungen zu liefern. Ausgangspunkt war die Grundidee, Sender und Empf{\"a}nger abwechselnd zu optimieren, bis keine weitere Verbesserung mehr eintritt. Numerische Ergebnisse werden anhand von Testinstanzen pr{\"a}sentiert und mit einem exakten Ansatz verglichen.}, subject = {Heuristiken; Ganzzahlige Programmierung; Quadratische Nebenbedingungen; Multistatisches Sonar; Netzplanung; Heuristics; Integer programming; Quadratic constraints; Multi-static sonar; Network planning; Ganzzahlige Optimierung; Heuristik; Netzplanung}, language = {de} } @masterthesis{Meier2019, type = {Bachelor Thesis}, author = {Meier, Yvonne}, title = {Ein gemischt-ganzzahliger Ansatz zur gleichm{\"a}ßigen Verkehrsauslastung eines Ballungsraums mittels Verschiebung der Schulanfangszeiten}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4802}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48023}, school = {BTU Cottbus - Senftenberg}, year = {2019}, abstract = {Die vorliegende Arbeit besch{\"a}ftigt sich mit der gleichm{\"a}ß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{\"u}lertransportproblem, d.h. der Aufgabe, Sch{\"u}ler innerhalb eines Systems zu einer bestimmten Zeit zu ihrer Schule zu transportieren. Die Staffelung der Schulanfangszeiten bietet eine M{\"o}glichkeit, dieses hohe Personenaufkommen gezielt zu kontrollieren und zu optimieren. Die gleichm{\"a}ßigere Auslastung eines Systems beeinflusst auch die Belastung im {\"o}ffentlichen Nahverkehr. Im Gegensatz zur Schaffung neuer Alternativen k{\"o}nnen so die vorhandenen Kapazit{\"a}ten effizienter eingesetzt werden, ohne das Angebot zu reduzieren. Durch das geringere punktuelle Aufkommen von Fahrg{\"a}sten kann der zur Verf{\"u}gung stehende Fuhrpark wirksamer genutzt werden. Zus{\"a}tzlich machen die zu den Stoßzeiten entlasteten Busse und Bahnen den {\"o}ffentlichen Personennahverkehr f{\"u}r andere Zielgruppen attraktiver. Im Rahmen dieser Arbeit wurde ein gemischt-ganzzahliger Ansatz zur Realisation dieser Aufgabe entwickelt. In Kapitel 1 wird zun{\"a}chst ein {\"U}berblick {\"u}ber verschiedene Betrachtungsweisen und Modelle f{\"u}r Sch{\"u}lertransporte und der Optimierung von Personenaufkommen gegeben, Kapitel 2 widmet sich den notwendigen mathematischen Grundlagen, die f{\"u}r den Ansatz wichtig sind. Im Anschluss werden die Modelle konzipiert und erl{\"a}utert. Die Ergebnisse werden dargestellt und analysiert, worauf abschließend ein Ausblick {\"u}ber die behandelte Problematik folgt.}, subject = {Mixed-Integer Programming; Operational Research; School Bell Scheduling; Optimization of Public Transportation; Gemischt-ganzzahlige Optimierung; Verkehrsplanung; Sch{\"u}lertransport}, language = {de} } @techreport{SchmidtFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {A two-time-level model for mission and flight planning of an inhomogeneous fleet of unmanned aerial vehicles}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5461}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54619}, year = {2021}, abstract = {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.}, subject = {Mixed-integer nonlinear programming; Mission Planning; Inhomogeneous Fleet; Time Windows; Linearization methods; Gemischt-ganzzahlige nichtlineare Programming; Missionsplanung; Inhomogene Flotte; Zeitfenster; Linearisierungsmethoden; Nichtlineare Optimierung; Tourenplanung; Flugk{\"o}rper}, language = {en} } @techreport{StieberFuegenschuh2019, author = {Stieber, Anke and F{\"u}genschuh, Armin}, title = {Dealing with time in the multiple traveling salesmen problem with moving targets}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4824}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48245}, year = {2019}, abstract = {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.}, subject = {Dynamic traveling salesmen problem; Moving targets; Time-relaxation; Integer linear programming; Second-order cone programming; Travelling-salesman-Problem}, language = {en} } @techreport{AuerDosaDulaietal.2019, author = {Auer, Peter and D{\´o}sa, Gy{\"o}rgy and Dulai, Tibor and F{\"u}genschuh, Armin and N{\"a}ser, Peggy and Ortner, Ronald and Werner-Stark, {\´A}gnes}, title = {A new heuristic and an exact approach for a production planning problem}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4827}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48278}, year = {2019}, abstract = {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.}, subject = {Production planning; Mixed-integer programming; Heuristics; Simulation; Fertigungsprogrammplanung; Heuristik; Optimierung}, language = {en} } @techreport{GnegelFuegenschuh2019, author = {Gnegel, Fabian and F{\"u}genschuh, Armin}, title = {An iterative graph expansion approach for the scheduling and routing of airplanes}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4806}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48069}, year = {2019}, abstract = {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.}, subject = {Mixed Integer Linear Programming; Operational Research; Vehicle Routing Problem; Time-Dependent Airplane Routing; Dynamic Graph Expansion; Routing; Mehrdepotproblem; Expandierender Graph}, language = {en} } @techreport{OclooFuegenschuhPamen2020, type = {Working Paper}, author = {Ocloo, Valentina E. and F{\"u}genschuh, Armin and Pamen, Olivier M.}, title = {A new mathematical model for a 3D container packing problem}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5088}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50880}, year = {2020}, abstract = {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{\"a}dt. F{\"u}r dieses Problem entwickeln und l{\"o}sen wir ein lineares gemischt-ganzzahliges Modell. Unser Modell ber{\"u}cksichtigt geometrische Randbedingungen, beispielsweise {\"U}berlappungsverbote, Orientierungs-Bedingungen und Randbedingungen f{\"u}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{\"a}llen wurden optimale L{\"o}sungen erzielt bzw. nah-optimale L{\"o}sungen mit beweisbar kleiner Optimalit{\"a}tsl{\"u}cke.}, subject = {Container packing problem; Mixed-integer programming; Box orientation; Non-overlapping; Center of gravity deviation; Optimierungsproblem; Container; Lineare Optimierung; Logistik}, language = {en} } @techreport{JohannsmannCraparoDiekenetal.2020, type = {Working Paper}, author = {Johannsmann, Leonie M. and Craparo, Emily M. and Dieken, Thor L. and F{\"u}genschuh, Armin and Seitner, Bj{\"o}rn O.}, title = {Stochastic mixed-integer programming for a spare parts inventory management problem}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5080}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50802}, year = {2020}, abstract = {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.}, subject = {Logisitcs; Scenario generation; Bestandsmanagement; Logistik; Ganzzahlige Optimierung; Stochastische Optimierung; Operations Research; Uncertainty; Warehouse management; Operations research; Two-stage stochastic optimization; Mixed-integer programming; Logistik; Szenario-Erzeugung; Unsicherheit; Lagermanagement; Gemischt-ganzzahlige Optimierung; Unternehmensforschung; Zweistufige stochastische Optimierung}, language = {en} } @masterthesis{Werger2019, type = {Bachelor Thesis}, author = {Werger, Tabea}, title = {Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4803}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48036}, school = {BTU Cottbus - Senftenberg}, year = {2019}, abstract = {Die Bachelorarbeit besch{\"a}ftigt sich mit der Erstellung eines m{\"o}glichst guten, zul{\"a}ssigen Stundenplans f{\"u}r eine Unteroffiziersschule der Bundeswehr. Die Bildungseinrichtung kann vorhandene Optimierungsprogramme f{\"u}r Stundenpl{\"a}ne nur teilweise zu Rate ziehen, da hier im Vergleich zu normalen Schulen und Universit{\"a}ten die Veranstaltungen nicht in einem Wochenzyklus stattfinden. Des Weiteren gibt es Spezialveranstaltungen, die nur an bestimmten Tagen besucht werden k{\"o}nnen. Zus{\"a}tzlich haben die zu absolvierenden Kurse eine fest vorgegebene Reihenfolge, die beachtet werden muss.}, subject = {Mixed-integer programming; Operational research; School time table planning; Ganzzahlige Optimierung; Stundenplanerstellung}, language = {de} } @techreport{BaehrBuhlRadowetal.2019, type = {Working Paper}, author = {B{\"a}hr, Martin and Buhl, Johannes and Radow, Georg and Schmidt, Johannes and Bambach, Markus and Breuß, Michael and F{\"u}genschuh, Armin}, title = {Stable honeycomb structures and temperature based trajectory optimization for wire-arc additive manufacturing}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5079}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50796}, year = {2019}, abstract = {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.}, subject = {Eikonal equation; Centroidal Voronoi tessellation; Additive manufacturing; Heat transmission; Mixed-integer linear programming; Geometric optimization; Additive Fertigung; Gemischt-ganzzahlige Programmierung; Geometrische Optimierung; Eikonal-Gleichung; Zentrierte Voronoi-Parkettierung; W{\"a}rmeleitung; Rapid Prototyping ; Eikonal; Ganzzahlige Optimierung; Geometrische Optimierung; W{\"a}rmeleitung}, language = {en} } @phdthesis{Gnegel2022, author = {Gnegel, Fabian}, title = {Refinement algorithms for time-dependent discrete optimization problems}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-6127}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61275}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {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.}, subject = {Discrete optimization; Mixed integer linear programming; Graph refinement; Branch and bound; Time-dependent airplane routing; Diskrete Optimierung; Gemischt-ganzzahlige lineare Programmierung; Verfeinerung von Graphen; Zeitabh{\"a}ngige Flugroutenplanung; Tourenplanung von E-Fahrzeugen; Ganzzahlige Optimierung; Tourenplanung; Travelling-salesman-Problem; Branch-and-Bound-Methode}, language = {en} } @techreport{SchmidtFuegenschuh2023, type = {Working Paper}, author = {Schmidt, Johannes and F{\"u}genschuh, Armin}, title = {Trajectory optimization for arbitrary layered geometries in wire-arc additive manufacturing}, doi = {10.26127/BTUOpen-6267}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-62678}, year = {2023}, abstract = {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.}, subject = {Mixed-integer programming; Trajektorie ; Partielle Differentialgleichung; Finite-Volumen-Methode; W{\"a}rmeleitung; Wire are additive manufacturing; Trajectory planning; Partial differential equations; Finite element method; Heat conduction; Gemischt-ganzzahlige Programmierung; Additive Draht-Lichtbogen-Fertigung,; Trajektorienplanung; Partielle Differenzialgleichungen; Finite-Elemente-Methode; W{\"a}rmeleitung}, language = {en} } @techreport{GnegelSchaudtClausenetal.2021, type = {Working Paper}, author = {Gnegel, Fabian and Schaudt, Stefan and Clausen, Uwe and F{\"u}genschuh, Armin}, title = {A 2D layered graph approach for scheduling delivery robots}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5493}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-54931}, year = {2021}, abstract = {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.}, subject = {Delivery robots; Electric vehicle routing problem; Graph refinement; Layered graphs; Partial recharging; Lieferroboter; Streckenplanung f{\"u}r elektrische Fahrzeuge; Graphenverfeinerung; Geschichtete Graphen; Partielles Aufladen; Mobiler Roboter; Tourenplanung; Optimierung}, language = {en} } @phdthesis{Stieber2022, author = {Stieber, Anke}, title = {The multiple traveling salesperson problem with moving targets}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-6110}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-61104}, school = {BTU Cottbus - Senftenberg}, year = {2022}, abstract = {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.}, subject = {Multiple traveling salesperson problem; Moving targets; Modeling of time; Online algorithms; Competitive analysis; Multiples Handlungsreisendenproblem; Bewegliche Ziele; Modellierung von Zeit; Online-Algorithmen; Kompetitivit{\"a}tsanalyse; Competitive analysis; Travelling-salesman-Problem}, language = {en} } @techreport{GnegelFuegenschuhHageletal.2019, author = {Gnegel, Fabian and F{\"u}genschuh, Armin and Hagel, Michael and Leyffer, Sven and Stiemer, Marcus}, title = {A solution framework for linear PDE-constrained mixed-integer problems}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5045}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-50453}, year = {2019}, abstract = {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.}, subject = {Mixed-integer linear programming; Partial differential equations; Finite-element methods; Convection-diffusion equation; Global optimal control; Gemischt-ganzzahlige lineare Programmierung; Globale Optimalsteuerung; Konvektions-Diffusions-Gleichung; Finite-Elemente-Methode; Partielle Differentialgleichungen; Optimale Kontrolle; Finite-Elemente-Methode; Lineare Optimierung; Konvektions-Diffusionsgleichung}, language = {en} } @techreport{SchmidtBuhlFuegenschuh2021, type = {Working Paper}, author = {Schmidt, Johannes and Buhl, Johannes and F{\"u}genschuh, Armin}, title = {A finite element approach for trajectory optimization in Wire-Arc Additive Manufacturing}, editor = {F{\"u}genschuh, Armin}, doi = {10.26127/BTUOpen-5575}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-55753}, year = {2021}, abstract = {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.}, subject = {Additive manufacturing; Heat equation; Path optimization; Finite element method; Mixed-integer linear programming; Additive Fertigung; Pfadoptimierung; W{\"a}rmeleitungsgleichung; Finite-Elemente-Methode; Gemischt-ganzzahlige lineare Programmierung; Rapid Prototyping ; W{\"a}rmeleitungsgleichung; Bahnplanung; Ganzzahlige lineare Optimierung; Finite-Elemente-Methode}, language = {en} } @techreport{FuegenschuhMuellenstedtSchmidt2019, author = {F{\"u}genschuh, Armin and M{\"u}llenstedt, Daniel and Schmidt, Johannes}, title = {Mission planning for unmanned aerial vehicles}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-4828}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-48285}, year = {2019}, abstract = {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.}, subject = {Mixed-integer nonlinear programming; Trajectory planning; Unmanned aerial vehicles; Linear approximation; Flugk{\"o}rper; Tourenplanung; Optimierung}, language = {en} } @techreport{GnegelFuegenschuh2020, type = {Working Paper}, author = {Gnegel, Fabian and F{\"u}genschuh, Armin}, title = {Branch-and-refine for solving time-dependent problems}, editor = {F{\"u}genschuh, Armin}, issn = {2627-6100}, doi = {10.26127/BTUOpen-5199}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-51995}, year = {2020}, abstract = {Einer der Standardans{\"a}tze zur L{\"o}sung zeitabh{\"a}ngiger diskreter Optimierungsprobleme, wie z.B. das Problem des Handlungsreisenden mit Zeitfenstern oder das K{\"u}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{\"a}nkungen bereits aufgrund seiner Topologie erf{\"u}llt sind und somit Algorithmen f{\"u}r die entsprechende zeitunabh{\"a}ngige Variante angewendet werden k{\"o}nnen. Der Nachteil dieses Ansatzes ist, dass die Mengen der Ecken und B{\"o}gen des zeitexpandierten Graphen viel gr{\"o}ßer sind als die des urspr{\"u}nglichen Graphen. In neueren Arbeiten hat sich jedoch gezeigt, dass f{\"u}r viele praktische Anwendungen eine partielle Expandierung des Graphen, die m{\"o}glicherweise zeitunm{\"o}gliche Pfade zul{\"a}sst, oft ausreicht, um eine beweisbar optimale L{\"o}sung zu finden. Diese Ans{\"a}tze verfeinern iterativ den urspr{\"u}nglichen Graphen und l{\"o}sen in jeder Iteration eine Relaxierung der zeitexpandierten Formulierung. Wenn die L{\"o}sung der aktuellen Relaxation alle Zeitbeschr{\"a}nkungen erf{\"u}llt, kann daraus eine optimale L{\"o}sung abgeleitet werden, und der Algorithmus terminiert. In dieser Arbeit stellen wir neue Ideen vor, die das {\"U}bertragen von Informationen {\"u}ber die optimale L{\"o}sung eines gr{\"o}beren Graphen zu einem verfeinerten Graphen erm{\"o}glichen und zeigen, wie diese in Algorithmen verwendet werden k{\"o}nnen. Genauer gesagt stellen wir einen neuen Algorithmus zur L{\"o}sung von MILP-Formulierungen (Mixed Integer Linear Program) von zeitabh{\"a}ngigen Problemen vor, der es erm{\"o}glicht, die Graphenverfeinerung w{\"a}hrend der Untersuchung des Branch-and-Bound Baums durchzuf{\"u}hren, anstatt jedes Mal neu zu starten, wenn die optimale L{\"o}sung sich als nicht zul{\"a}ssig herausgestellt hat. Um die praktische Relevanz dieses Algorithmus zu demonstrieren, pr{\"a}sentieren wir Ergebnisse von numerische Experimenten seiner Anwendung auf das K{\"u}rzeste Wege Problem mit Zeitfenstern und das Problem des Handlungsreisenden mit Zeitfenstern.}, subject = {Graphenverfeinerung; Branch-and-Bound; K{\"u}rzeste Wege Problem mit Zeitfenstern; Problem des Handlungsreisenden mit Zeitfenstern; Graph refinement; Branch-and-bound; Shortest path problem with time-windows; Travelling salesman problem with time-windows; Branch-and-Bound-Methode; K{\"u}rzester-Weg-Problem; Travelling-salesman-Problem}, language = {en} } @techreport{DeeFuegenschuhKaimakamis2021, type = {Working Paper}, author = {Dee, Robin and F{\"u}genschuh, Armin and Kaimakamis, George}, title = {The unit re-balancing problem}, doi = {10.26127/BTUOpen-5658}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-56587}, year = {2021}, abstract = {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.}, subject = {Re-balancing problem; Efficiency; Mixed-integer linear programming; Bi-criteria optimization; Umverteilungsproblem; Effizienz; Gemischt-ganzzahlige Programmierung; Bikriterielle Optimierung; Ganzzahlige Optimierung; Optimierungsproblem; Effizienz}, language = {en} } @masterthesis{Zhong2023, type = {Bachelor Thesis}, author = {Zhong, Lingyu}, title = {Set Covering Probleme in der Funknetzplanung}, doi = {10.26127/BTUOpen-6355}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-63556}, school = {BTU Cottbus - Senftenberg}, year = {2023}, abstract = {In dieser Bachelorarbeit wird das Problem der Auswahl von Antennenstandorten f{\"u}r eine maximale r{\"a}umliche Abdeckung in 5G-Funknetzen untersucht. Das Hauptziel besteht darin, eine effiziente L{\"o}sung f{\"u}r dieses kombinatorische Optimierungsproblem zu finden, indem es als Partial Set Covering Problem formuliert und gel{\"o}st wird. Die Arbeit gliedert sich in zwei Teile: Der erste Teil bietet eine Einf{\"u}hrung in die mathematischen Grundlagen des Partial Set Covering Problems, einschließlich Definitionen, Formulierung und L{\"o}sungsverfahren. Im zweiten Teil wird ein praktischer Ansatz zur L{\"o}sung dieses Problems pr{\"a}sentiert, wobei realen Instanzen f{\"u}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{\"o}st werden? Die Ergebnisse dieser Arbeit tragen dazu bei, fundierte Entscheidungen {\"u}ber den Aufbau von 5G-Netzen zu treffen und die Netzwerkabdeckung unter Ber{\"u}cksichtigung von Nebenbedingungen zu maximieren.}, subject = {5G-Funknetze; Antennenstandort-Optimierung; Kombinatorische Optimierung; Partial Set Covering Problem; Simulated-Annealing-Algorithmus; 5G radio networks; Antenna site optimization; Combinatorial optimization; Partial set covering problem; Simulated annealing algorithm; 5G; Funknetz; Antenne; Kombinatorische Optimierung}, language = {de} }