Refine
Year of publication
Has Fulltext
- yes (25)
Keywords
- MINT (4)
- Mathematische Modellierung (4)
- Schule (4)
- Multiobjective optimization (3)
- Approximation (2)
- Hypervolume (2)
- Subset selection (2)
- combinatorial optimization (2)
- connectedness (2)
- k-link shortest path (2)
Faculty / Organisational entity
Das MINT-EC-Girls-Camp: Math-Talent-School richtet sich an mathematikbegeisterte Schülerinnen von MINT-EC-Schulen, die Einblicke in die Berufswelt von Mathematikerinnen und Mathematikern bekommen möchten. Die Veranstaltung veranschaulicht den Schülerinnen die steigende Relevanz angewandter mathematischer Forschungsgebiete, wie der Techno- und der Wirtschaftsmathematik. Sie soll dazu dienen, Schüler:innen die Bedeutung mathematischer Arbeitsweisen in der heutigen Berufswelt, insbesondere in Industrie und Wirtschaft, begreifbar zu machen. Die Talent-School wird organisiert von MINT-EC und dem Felix-Klein-Zentrum für Mathematik. Die fachwissenschaftliche Betreuung der Schülerinnen während dieser Talent-School wurde durch Mitarbeitende des Kompetenzzentrums für Mathematische Modellierung in MINT-Projekten in der Schule (KOMMS) der TU Kaiserslautern und des Fraunhofer ITWM umgesetzt. In diesem Report beschreiben wir die Projekte, die während der Talent-School im Oktober 2022 durchgeführt wurden.
Seit 1993 veranstaltet der Fachbereich Mathematik der TU Kaiserslautern jährlich die mathematischen Modellierungswochen. Die Veranstaltung erwuchs parallel zu der steigenden Relevanz angewandter mathematischer Forschungsgebiete, wie der Technomathematik und der Wirtschaftsmathematik. Sie soll dazu dienen, Schülerinnen und Schülern die Bedeutung mathematischer Arbeitsweisen in der heutigen Berufswelt, insbesondere in Industrie und Wirtschaft, begreifbar zu machen. Darüber hinaus bietet die Modellierungswoche den teilnehmenden Lehrkräften einen Einblick in die Projektarbeit mit offenen Fragestellungen im Rahmen der mathematischen Modellierung. In diesem Report beschreiben wir die Projekte, die während der Modellierungswoche im Dezember 2021 durchgeführt wurden. Der Themenschwerpunkt der Veranstaltung lautete "Wetter und Katastrophenschutz".
In a widely-studied class of multi-parametric optimization problems, the objective value of each solution is an affine function of real-valued parameters. Then, the goal is to provide an optimal solution set, i.e., a set containing an optimal solution for each non-parametric problem obtained by fixing a parameter vector. For many multi-parametric optimization problems, however, an optimal solution set of minimum cardinality can contain super-polynomially many solutions. Consequently, no polynomial-time exact algorithms can exist for these problems even if P=NP. We propose an approximation method that is applicable to a general class of multi-parametric optimization problems and outputs a set of solutions with cardinality polynomial in the instance size and the inverse of the approximation guarantee. This method lifts approximation algorithms for non-parametric optimization problems to their parametric version and provides an approximation guarantee that is arbitrarily close to the approximation guarantee of the approximation algorithm for the non-parametric problem. If the non-parametric problem can be solved exactly in polynomial time or if an FPTAS is available, our algorithm is an FPTAS. Further, we show that, for any given approximation guarantee, the minimum cardinality of an approximation set is, in general, not ℓ-approximable for any natural number ℓ less or equal to the number of parameters, and we discuss applications of our results to classical multi-parametric combinatorial optimizations problems. In particular, we obtain an FPTAS for the multi-parametric minimum s-t-cut problem, an FPTAS for the multi-parametric knapsack problem, as well as an approximation algorithm for the multi-parametric maximization of independence systems problem.
Many real-world optimization and decision-making problems comprise several, partly conflicting objective functions. The English saying “Quality has its price” is just as true on a large scale as it is in private sphere and, therefore, quality and price are a typical pair of conflicting objective functions that are very common in applications. Yet, in industrial applications, both quality and cost may be understood in the specific context and differ whether a transportation, a production, or a planning problem is considered. Other objective functions that are receiving increasing attention in real-world decision-making situations are, for example, robustness, time, sustainability, adaptability, or longevity.
This article investigates a network interdiction problem on a tree network: given a subset of nodes chosen as facilities, an interdictor may dissect the network by removing a size-constrained set of edges, striving to worsen the established facilities best possible. Here, we consider a reachability objective function, which is closely related to the covering objective function: the interdictor aims to minimize the number of customers that are still connected to any facility after interdiction. For the covering objective on general graphs, this problem is known to be NP-complete (Fröhlich and Ruzika In: On the hardness of covering-interdiction problems. Theor. Comput. Sci., 2021). In contrast to this, we propose a polynomial-time solution algorithm to solve the problem on trees. The algorithm is based on dynamic programming and reveals the relation of this location-interdiction problem to knapsack-type problems. However, the input data for the dynamic program must be elaborately generated and relies on the theoretical results presented in this article. As a result, trees are the first known graph class that admits a polynomial-time algorithm for edge interdiction problems in the context of facility location planning.
Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the
Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time
solvability of a certain auxiliary problem determines the class of multiobjective optimization
problems that admit a polynomial-time computable (1+ε, . . . , 1+ε)-approximate Pareto set
(also called an ε-Pareto set). Similarly, in this article, we characterize the class ofmultiobjective
optimization problems having a polynomial-time computable approximate ε-Pareto set
that is exact in one objective by the efficient solvability of an appropriate auxiliary problem.
This class includes important problems such as multiobjective shortest path and spanning
tree, and the approximation guarantee we provide is, in general, best possible. Furthermore,
for biobjective optimization problems from this class, we provide an algorithm that computes
a one-exact ε-Pareto set of cardinality at most twice the cardinality of a smallest such set and
show that this factor of 2 is best possible. For three or more objective functions, however,
we prove that no constant-factor approximation on the cardinality of the set can be obtained
efficiently.
This article is dedicated to the weight set decomposition of a multiobjective (mixed-)integer linear problem with three objectives. We propose an algorithm that returns a decomposition of the parameter set of the weighted sum scalarization by solving biobjective subproblems via Dichotomic Search which corresponds to a line exploration in the weight set. Additionally, we present theoretical results regarding the boundary of the weight set components that direct the line exploration. The resulting algorithm runs in output polynomial time, i.e. its running time is polynomial in the encoding length of both the input and output. Also, the proposed approach can be used for each weight set component individually and is able to give intermediate results, which can be seen as an “approximation” of the weight set component. We compare the running time of our method with the one of an existing algorithm and conduct a computational study that shows the competitiveness of our algorithm. Further, we give a state-of-the-art survey of algorithms in the literature.
In a (linear) parametric optimization problem, the objective value of each feasible solution is an affine function of a real-valued parameter and one is interested in computing a solution for each possible value of the parameter. For many important parametric optimization problems including the parametric versions of the shortest path problem, the assignment problem, and the minimum cost flow problem, however, the piecewise linear function mapping the parameter to the optimal objective value of the corresponding non-parametric instance (the optimal value function) can have super-polynomially many breakpoints (points of slope change). This implies that any optimal algorithm for such a problem must output a super-polynomial number of solutions. We provide a method for lifting approximation algorithms for non-parametric optimization problems to their parametric counterparts that is applicable to a general class of parametric optimization problems. The approximation guarantee achieved by this method for a parametric problem is arbitrarily close to the approximation guarantee of the algorithm for the corresponding non-parametric problem. It outputs polynomially many solutions and has polynomial running time if the non-parametric algorithm has polynomial running time. In the case that the non-parametric problem can be solved exactly in polynomial time or that an FPTAS is available, the method yields an FPTAS. In particular, under mild assumptions, we obtain the first parametric FPTAS for each of the specific problems mentioned above and a (3/2 + ε) -approximation algorithm for the parametric metric traveling salesman problem. Moreover, we describe a post-processing procedure that, if the non-parametric problem can be solved exactly in polynomial time, further decreases the number of returned solutions such that the method outputs at most twice as many solutions as needed at minimum for achieving the desired approximation guarantee.
Die MINT-EC-Girls-Camp: Math-Talent-School ist eine vom Fraunhofer Institut für Techno- und Wirtschaftsmathematik (ITWM) initiierte Veranstaltung, die regelmäßig als Kooperation zwischen dem Felix-Klein-Zentrum für Mathematik und dem Verein mathematisch-naturwissenschaftlicher Excellence-Center an Schulen e.V. (Verein MINT-EC) durchgeführt wird. Die methodisch-didaktische Konzeption der Math-Talent-Schools erfolgt durch das Kompetenzzentrum für Mathematische Modellierung in MINT-Projekten in der Schule (KOMMS), einer wissenschaftlichen Einrichtung des Fachbereichs Mathematik der Technischen Universität Kaiserslautern. Die inhaltlich-organisatorische Ausführung übernimmt das Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM in enger Abstimmung und Kooperation von Wissenschaftlern der Technischen Universität und des Fraunhofer ITWM. Die MINT-EC-Girls-Camp: Math-Talent-School hat zum Ziel, Mathematik-interessierten Schülerinnen einen Einblick in die Arbeitswelt von Mathematikerinnen und Mathematikern zu geben. In diesem Artikel stellen wir die Math-Talent-School vor. Hierfür werden die fachlichen und fachdidaktischen Hintergründe der Projekte beleuchtet, der Ablauf der Veranstaltung erläutert und ein Fazit gezogen.
Dieser Beitrag beschreibt eine Lernumgebung für Schülerinnen und Schüler der Unter- und Mittelstufe mit einem Schwerpunkt im Fach Mathematik. Das Thema dieser Lernumgebung ist die Simulation von Entfluchtungsprozessen im Rahmen von Gebäudeevakuierungen. Dabei wird das Konzept eines zellulären Automaten vermittelt, ohne dabei Programmierkenntnisse vorauszusetzen oder anzuwenden. Anhand dieses speziellen Simulationswerkzeugs des zellulären Automaten werden Eigenschaften, Kenngrößen sowie Vor- und Nachteile von Simulationen im Allgemeinen thematisiert. Dazu gehören unter anderem die experimentelle Datengewinnung, die Festlegung von Modellparametern, die Diskretisierung des zeitlichen und räumlichen Betrachtungshorizonts sowie die zwangsläufig auftretenden (Diskretisierungs-)Fehler, die algorithmischen Abläufe einer Simulation in Form elementarer Handlungsanweisungen, die Speicherung und Visualisierung von Daten aus einer Simulation sowie die Interpretation und kritische Diskussion von Simulationsergebnissen. Die vorgestellte Lernumgebung ermöglicht etliche Variationen zu weiteren Aspekten des Themas „Evakuierungssimulation“ und bietet dadurch auch vielfältige Differenzierungsmöglichkeiten.
The hypervolume subset selection problem consists of finding a subset, with a given cardinality \(k\), of a set of nondominated points that maximizes the hypervolume indicator. This problem arises in selection procedures of evolutionary algorithms for multiobjective optimization, for which practically efficient algorithms are required. In this article, two new formulations are provided for the two-dimensional variant of this problem.
The first is a (linear) integer programming formulation that can be solved by solving its linear programming relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with the Monge property that can be solved by dynamic programming in \(\mathcal{O}(n(k + \log n))\) time. This improves upon the \(\mathcal{O}(n^2k)\) result of Bader (2009), and matches the recent result of Bringmann et al. (2014), which was developed independently from this work using different techniques. Moreover, it is shown that these bounds may be further improved under mild conditions on \(k\).
The hypervolume subset selection problem consists of finding a subset, with a given cardinality, of a nondominated set of points that maximizes the hypervolume indicator. This problem arises in selection procedures of population-based heuristics for multiobjective optimization, and for which practically efficient algorithms are strongly required. In this article, we provide two new formulations for the two-dimensional variant of this problem.
The first is an integer programming formulation that can be solved by solving its linear relaxation. The second formulation is a \(k\)-link shortest path formulation on a special digraph with Monge property that can be solved by dynamic programming in \(\mathcal{O}(n^2)\) time complexity. This improves upon the existing result of \(O(n^3)\) in Bader.
A new algorithm for optimization problems with three objective functions is presented which computes a representation for the set of nondominated points. This representation is guaranteed to have a desired coverage error and a bound on the number of iterations needed by the algorithm to meet this coverage error is derived. Since the representation does not necessarily contain nondominated points only, ideas to calculate bounds for the representation error are given. Moreover, the incorporation of domination during the algorithm and other quality measures are discussed.
We consider a variant of a knapsack problem with a fixed cardinality constraint. There are three objective functions to be optimized: one real-valued and two integer-valued objectives. We show that this problem can be solved efficiently by a local search. The algorithm utilizes connectedness of a subset of feasible solutions and has optimal run-time.
In a dynamic network, the quickest path problem asks for a path minimizing the time needed to send a given amount of flow from source to sink along this path. In practical settings, for example in evacuation or transportation planning, the reliability of network arcs depends on the specific scenario of interest. In this circumstance, the question of finding a quickest path among all those having at least a desired path reliability arises. In this article, this reliable quickest path problem is solved by transforming it to the restricted quickest path problem. In the latter, each arc is associated a nonnegative cost value and the goal is to find a quickest path among those not exceeding a predefined budget with respect to the overall (additive) cost value. For both, the restricted and reliable quickest path problem, pseudopolynomial exact algorithms and fully polynomial-time approximation schemes are proposed.
We consider multiple objective combinatiorial optimization problems in which the first objective is of arbitrary type and the remaining objectives are either bottleneck or k-max objective functions. While the objective value of a bottleneck objective is determined by the largest cost value of any element in a feasible solution, the kth-largest element defines the objective value of the k-max objective. An efficient solution approach for the generation of the complete nondominated set is developed which is independent of the specific combinatiorial problem at hand. This implies a polynomial time algorithm for several important problem classes like shortest paths, spanning tree, and assignment problems with bottleneck objectives which are known to be NP-hard in the general multiple objective case.
In a dynamic network, the quickest path problem asks for a path such that a given amount of flow can be sent from source to sink via this path in minimal time. In practical settings, for example in evacuation or transportation planning, the problem parameters might not be known exactly a-priori. It is therefore of interest to consider robust versions of these problems in which travel times and/or capacities of arcs depend on a certain scenario. In this article, min-max versions of robust quickest path problems are investigated and, depending on their complexity status, exact algorithms or fully polynomial-time approximation schemes are proposed.
Selection of new projects is one of the major decision making activities in any company. Given a set of potential projects to invest, a subset which matches the company's strategy and internal resources best has to be selected. In this paper, we propose a multicriteria model for portfolio selection of projects, where we take into consideration that each of the potential projects has several - usually conflicting - values.
Connectedness of efficient solutions is a powerful property in multiple objective combinatorial optimization since it allows the construction of the complete efficient set using neighborhood search techniques. In this paper we show that, however, most of the classical multiple objective combinatorial optimization problems do not possess the connectedness property in general, including, among others, knapsack problems (and even several special cases of knapsack problems) and linear assignment problems. We also extend already known non-connectedness results for several optimization problems on graphs like shortest path, spanning tree and minimum cost flow problems. Different concepts of connectedness are discussed in a formal setting, and numerical tests are performed for different variants of the knapsack problem to analyze the likelihood with which non-connected adjacency graphs occur in randomly generated problem instances.
In this paper, theory and algorithms for solving the multiple objective minimum cost flow problem are reviewed. For both the continuous and integer case exact and approximation algorithms are presented. In addition, a section on compromise solutions summarizes corresponding results. The reference list consists of all papers known to the autheors which deal with the multiple objective minimum cost flow problem.
In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature.