@phdthesis{Beisegel2020, author = {Beisegel, Jesse}, title = {Convexity in graphs: vertex order characterisations and graph searching}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-51452}, school = {BTU Cottbus - Senftenberg}, year = {2020}, abstract = {We study convexities designed to characterise some of the most fundamental classes of graphs. To this end, we present some known results on this topic in a slightly different form, so as to give a homogeneous representation of a very disparate field. Furthermore, we present some new results on the Caratheodory number of interval graphs and also give a more or less exhaustive account of everything that is known in this context on AT-free graphs, including new results on characterising linear vertex orders and the structure of the intervals of this class. We introduce the new class of bilateral AT-free graphs which is motivated by the linear order characterisation and the convexity used to describe AT-free graphs. We discuss their relation to other known classes and consider the complexity of recognition. Furthermore, as a consequence of notions from abstract convexity we present algorithmic results with regards to some natural subclasses of these. As an application of notion of an extreme vertex of a convex geometry, we discuss structural aspects of avoidable vertices in graphs, which form a generalisation of simplicial vertices. This includes a characterisation of avoidable vertices as simplicial vertices in some minimal triangulation of the graph and a new proof of the existence result. Furthermore, we discuss the algorithmic issues regarding the problem of efficient computation of avoidable vertices in a given graph. This is complemented by an algorithmic application of the concept of avoidable vertices to the maximum weight clique problem, by identifying a rather general class of graphs in which every avoidable vertex is bisimplicial. This leads to a polynomial-time algorithm for the maximum weight clique problem in this class of graphs. Implications of this approach for digraphs are also discussed. All of these results lead to a conjecture concerning the generalisation of avoidable vertices to avoidable paths and we prove this conjecture for paths of length less or equal to two. Finally, we analyse the properties of many different and widely used forms of graph search. Here, we discuss the problem of recognising whether a given vertex can be the last vertex visited by some fixed graph search. Moreover, we present some new aspects of the problem of deciding whether a given spanning tree of a graph is a graph search tree of a particular type of search. We generalise the concept of such trees to many well-known searches and give a broad analysis of the computational complexity of this problem. Both of these discussions are motivated by the use of graph searches in the context of computing properties of convexity.}, subject = {Graph convexity; Convex geometry; Graph searching; Vertex order characterisation; Asteroidal triples; Asteroidale Tripel; Lineare Knotenordnung; Graphensuche; Konvexe Geometrie; Konvexit{\"a}t; Graph; Konvexit{\"a}t; Konvexe Geometrie}, language = {en} } @phdthesis{Schmidt2024, author = {Schmidt, Johannes}, title = {The mission and flight planning problem : a physics-based MILP routing approach for an inhomogeneous fleet of unmanned aerial vehicles with collision-free trajectories}, doi = {10.26127/BTUOpen-6841}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-68415}, school = {BTU Cottbus - Senftenberg}, year = {2024}, abstract = {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.}, subject = {Mixed-integer linear programming; Trajectory optimization; Inter-sample avoidance; Unmanned aerial vehicles; Gemischt-ganzzahlige lineare Programmierung; Trajektorienoptimierung; Kollisionsvermeidung zwischen Zeitschritten; Unbemannte Luftfahrzeuge; Flugk{\"o}rper; Optimierungsproblem; Strategische Planung; Kollisionsschutz; Trajektorie }, language = {en} } @phdthesis{Scheffler2023, author = {Scheffler, Robert}, title = {Ready to order? : on vertex and edge orderings of graphs}, doi = {10.26127/BTUOpen-6301}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus4-63019}, school = {BTU Cottbus - Senftenberg}, year = {2023}, abstract = {Vertex and edge orderings of graphs are commonly used in algorithmic graph theory. Such orderings can encode structural properties of graphs in a condensed way and, thus, they can be used to process a graph efficiently. A common approach to find particular vertex orderings are graph searches. Here, we study the complexity of deciding whether vertex orderings with special properties can be found by particular graph searches. The properties of these orderings concern their end-vertices, their search trees or constraints encoded by partial orders. Many graph classes can be characterized via special vertex orderings. We introduce another example, the semi-proper interval graphs, generalizations of connected proper interval graphs that are characterized via special variants of perfect elimination orderings. We study the structure of these graphs, present a linear-time recognition algorithm and show that they share some strong properties on Hamiltonian paths and cycles with proper interval graphs. We also generalize the notion of graph classes to the case of edge-weighted graphs. A weighted graph is a member of such a weighted class if subgraphs containing edges of particular weights are members of the respective unweighted graph class. We present conditions on an unweighted graph class that ensure a linear-time recognition algorithm for its corresponding weighted graph class. This conditions make use of a novel edge monotonicity and of particular edge orderings. We apply this result to three well-known graph classes, namely split graphs, threshold graphs, and chain graphs. Finally, we consider dynamic algorithms on threshold and chain graphs. These algorithms update certain properties of a graph after small modifications are applied to its vertex or edge set. We present certifying dynamic recognition algorithms of these classes, i.e., if the graph leaves the class after the modification, we can prove this by providing a forbidden induced subgraph of bounded size. Building on these results, we extend the notion of dynamic recognition algorithms to whole sets of edges and vertices. Furthermore, we present dynamic algorithms for the Hamiltonian path and cycle problems.}, subject = {Graph search; Graphensuche; Dynamic algorithm; Dynamischer Algorithmus; Edge ordering; Kantenordnung; Vertex ordering; Knotenordnung; Weighted graph; Gewichteter Graph; Graphentheorie; Graphenklasse}, language = {en} } @phdthesis{Strehler2011, author = {Strehler, Martin}, title = {Signalized flows - optimizing traffic signals and guideposts and related network flow problems}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-23637}, school = {BTU Cottbus - Senftenberg}, year = {2011}, abstract = {Guideposts and traffic signals are important devices for controlling inner-city traffic and their optimized operation is essential for efficient traffic flow without congestion. In this thesis, we develop a mathematical model for guideposts and traffic signals in the context of network flow theory. Guideposts lead to confluent flows where each node in the network may have at most one outgoing flow-carrying arc. The complexity of finding maximum confluent flows is studied and several polynomial time algorithms for special graph classes are developed. For traffic signal optimization, a cyclically time-expanded model is suggested which provides the possibility of the simultaneous optimization of offsets and traffic assignment. Thus, the influence of offsets on travel times can be accounted directly. The potential of the presented approach is demonstrated by simulation of real-world instances.}, subject = {Stadtverkehr; Verkehrsablauf; Netzwerkfluss; Optimierung; Netzwerkfluss; Verkehrsfluss; Konfluenter Fluss; Lichtsignalanlagenoptimierung; Optimierung von Wegweisern; Network flow; Traffic flow; Confluent flow; Traffic signal optimization; Flow with path restrictions}, language = {en} } @phdthesis{Reich2014, author = {Reich, Alexander}, title = {Cycle bases of graphs and spanning trees with many leaves - complexity results on planar and regular graphs}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:co1-opus-30692}, school = {BTU Cottbus - Senftenberg}, year = {2014}, abstract = {A cycle basis of a graph is a basis of its cycle space, the vector space which is spanned by the cycles of the graph. Practical applications for cycle bases are for example the optimization of periodic timetables, electrical engineering, and chemistry. Often, cycle bases belong to the input of algorithms concerning these fields. In these cases, the running time of the algorithm can depend on the size of the given cycle basis. In this thesis, we study the complexity of finding minimum cycle bases of several types on different graph classes. As a main result, we show that the problem of minimizing strictly fundamental cycle bases on planar graphs is NP-complete. We also give a similarly structured proof for problem of finding a maximum leaf spanning tree on the very restricted class of cubic planar graphs. Additionally, we show that this problem is APX-complete on k-regular graphs for odd k greater than 3. Furthermore, we classify types of robust cycle bases and study their relationship to fundamental cycle bases.}, subject = {Planarer Graph; Zyklenraum; NP-vollst{\"a}ndiges Problem; Spannb{\"a}ume mit vielen Bl{\"a}ttern; Minimale streng fundamentale Kreisbasen; NP-Vollst{\"a}ndigkeit; APX-Vollst{\"a}ndigkeit; Planare Graphen; Maximum leaf spanning tree; Minimum strictly fundamental cycle basis; NP-completeness; APX-completeness; Planar graphs}, 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} } @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} } @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} }