FG Ingenieurmathematik und Numerik der Optimierung
Refine
Year of publication
Document Type
Way of publication
- Open Access (12)
Keywords
- digital filters (4)
- filter design (4)
- Hamiltonian path (2)
- intensity modulated radiation therapy (2)
- semi-infinite programming (2)
- Additive manufacturing (1)
- Additive manufacturing Centroidal, Voronoi tessellation, Energy minimisation, Geometric optimisation, Eikonal equation, Fast marching (1)
- Centroidal Voronoi tesselation (1)
- Eikonal equation (1)
- Engineering, general (1)
Institute
When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example, one could decide whether a Hamiltonian path exists for a fixed starting point, or that some vertices are visited before another vertex. We consider the problem of finding a Hamiltonian path that observes all precedence constraints given in a partial order on the vertex set. We show that this problem is NP-complete even if restricted to complete bipartite graphs and posets of height 2. In contrast, for posets of width k there is a known O(k^2 n^k) algorithm for arbitrary graphs with n vertices. We show that it is unlikely that the running time of this algorithm can be improved significantly, i.e., there is no f(k) n^o(k) time algorithm under the assumption of the Exponential Time Hypothesis. Furthermore, for the class of outerplanar graphs, we give an O(n^2) algorithm for arbitrary posets.
In the highly dynamic environment of military operations, efficient medical evacuation (MEDEVAC) of casualties is a critical strategic challenge. This paper presents a method for planning MEDEVAC missions using mathematical optimization and gamification. By applying Mixed-Integer Programming (MIP), a mathematical optimization technique, to solve a MEDEVAC dispatching and routing problem, a structured approach to decision making in emergency situations is presented. Our MIP model enables the detailed consideration of operational conditions and the mission support with combat helicopters as escorts, and thus improves the strategic planning and efficiency of MEDEVAC operations. When it comes to balance mission safety versus execution speed, we will enter the realm of multicriteria optimization models. As a further aspect, the role of gamification is emphasized by developing a board game that simulates the planning task and thus promotes understanding of the planning software. This approach allows planners to compare the quality of their manual planning with the computer-generated solution, improve their own planning skills and realize the benefits of software support for automated, AI- (Artificial Intelligence-) -assisted planning.
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width parameters for which the ordinary problems Hamiltonian Path and Hamiltonian Cycle are in FPT. In particular, we focus on parameters that describe how many vertices and edges have to be deleted to become a member of a certain graph class. We show that the problems are W[1]-hard for such restricted cases as vertex distance to path and vertex distance to clique. We complement these results by showing that the problems can be solved in XP time for vertex distance to outerplanar and vertex distance to block. Furthermore, we present some FPT algorithms, e.g., for edge distance to block. Additionally, we prove para-NP-hardness when considered with the edge clique cover number.