70 search hits
-
A bijection between the d-dimensional simplices with distances in {1,2} and the partitions of d+1
(2005)
-
Christian Haase
Sascha Kurz
- We give a construction for the d-dimensional simplices with all distances in {1,2} from the set of partitions of d+1.
-
A generalized job-shop problem with more than one resource demand per task
(2011)
-
Joachim Schauer
Cornelius Schwarz
- We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.
-
A homotopy argument and its applications to the transformation rule for bi-Lipschitz mappings, the Brouwer fixed point theorem and the Brouwer degree
(2005)
-
Christian G. Simader
- The main purpose of the paper is to present an elementary self-contained proof of the change of variables formula for injective, locally bi-Lipschitz mappings. The proof is based on a homotopy argument. Various properties of bi-Lipschitz mappings are studied. As a by-product Lipschitz variants of the classical implicit function theorem and the local diffeomorphism theorem are proved. With the help of the homotopy argument a simple proof is given of Brouwer’s fixed point theorem and the main properties of Brouwer’s degree of mapping.
-
A note on Erdös-Diophantine graphs and Diophantine carpets
(2005)
-
Axel Kohnert
Sascha Kurz
- A Diophantine figure is a set of points on the integer grid $\mathbb{Z}^{2}$ where all mutual Euclidean distances are integers. We also speak of Diophantine graphs. The vertices are points in $\mathbb{Z}^{2}$ (the coordinates)and the edges are labeled with the distance between the two adjacent vertices, which is integral. In this language a Diophantine figure is a complete Diophantine graph. Two Diophantine graphs are equivalent if they only differ by translation or rotation of vertices. Due to a famous theorem of Erdös and Anning there are complete Diophantine graphs which are not contained in larger ones. We call them Erdös-Diophantine graphs. A special class of Diophantine graphs are Diophantine carpets. These are planar triangulations of a subset of the integer grid. We give an effective construction for Erdös-Diophantine graphs and characterize the chromatic number of Diophantine carpets.
-
A strictly feasible sequential convex programming method
(2011)
-
Sonja Lehmann
- In free material optimization (FMO), one tries to find the best mechanical structure by minimizing the weight or by maximizing the stiffness with respect to given load cases. Design variables are the material properties represented by elasticity tensors or elementary material matrices, respectively, based on a given finite element discretization. Material properties are as general as possible, i.e., anisotropic, leading to positive definite elasticity tensors, which may be arbitrarily small in case of vanishing material. To guarantee a positive definite global stiffness matrix for computing design constraints, it is required that all iterates of an optimization algorithm retain positive definite tensors. Otherwise, some constraints, e.g., the compliance, cannot be evaluated and the algorithm fails. FMO problems are generalizations of topology optimization problems. The goal of topology optimization is to find the stiffest structure subject to given loads and a limited amount of material. In contrast to FMO the material is explicitly given and cannot vary. Based on a finite element discretization, in each element it is decided whether to use material or not. The regions with vanishing material are interpreted as void. The resulting optimization problem can be solved by numerous efficient nonlinear optimization methods, for example sequential convex programming methods. Sequential convex programming (SCP) formulates separable and strictly convex nonlinear subproblems iteratively by approximating the objective and the constraints. Lower and upper asymptotes are introduced to truncate the feasible region. Due to the special structure, the resulting subproblems can be solved efficiently by appropriate methods, e.g., interior point methods. To ensure global convergence, a line search procedure is introduced. Moreover, an active set strategy is applied to reduce computation time. The iterates of SCP are not guaranteed to be inside the corresponding feasible region described by the constraints. As a consequence it is not able to solve free material optimization problems as the compliance function is only well-defined on the feasible region of some of the constraints. We propose a modification of a SCP method that ensures feasibility with respect to a given set of inequality constraints. The resulting procedure is called feasible sequential convex programming method (SCPF). SCPF expands the resulting subproblems by additional nonlinear constraints, that are passed to the subproblem directly to ensure their feasibility in each iteration step. They are referred as feasibility constraints. In addition, other constraints may be violated within the optimization process. As globalization technique a line search procedure is used to ensure convergence. The resulting subproblems can be solved efficiently taking the sparse structure into account. Moreover, semidefinite constraints have to be replaced by nonlinear ones, such that SCPF is applicable. SCPF successfully solved FMO problems with up to 120.000 variables and 60.000 constraints. Within a theoretical analysis global convergence of SCPF is shown for convex feasibility constraints.
-
A survey of the higher Stasheff-Tamari orders
(2012)
-
Jörg Rambau
Victor Reiner
- The Tamari lattice, thought as a poset on the set of triangulations of a convex polygon with n vertices, generalizes to the higher Stasheff-Tamari orders on the set of triangulations of a cyclic d-dimensional polytope having n vertices. This survey discusses what is known about these orders, and what one would like to know about them.
-
Algebraische Approximation von Kählermannigfaltigkeiten
(2010)
-
Florian Schrack
- Eine kompakte komplexe Mannigfaltigkeit heißt algebraisch approximierbar, wenn sie beliebig kleine projektive Deformationen besitzt. Eine natürliche Fragestellung ist, ob jede kompakte Kählermannigfaltigkeit algebraisch approximierbar ist. Während dies in Dimension 2 nach den Arbeiten von Kodaira richtig ist, hat Voisin vierdimensionale Gegenbeispiele gefunden. In Dimension 3 ist die Frage noch offen. Ziel der vorliegenden Arbeit ist es, den dreidimensionalen Fall etwas näher zu beleuchten. Dazu wird algebraische Approximierbarkeit zunächst von einem allgemeinen Standpunkt aus betrachtet. Es werden Funktorialitätsfragen untersucht, also der Zusammenhang zwischen algebraischer Approximierbarkeit der Quelle und des Ziels gewisser holomorpher Abbildungen, und Ergebnisse für verschiedene Klassen von Abbildungen erzielt, wie etwa Aufblasungen, endliche Abbildungen, Faserungen und Morikontraktionen. Als Fallstudie einer konkreten Klasse von Kählerdreifaltigkeiten werden anschließend Konikbündel über Kählerflächen untersucht, die in natürlicher Weise in der Moritheorie auftreten. Nach dem Beweis einiger grundlegender Tatsachen über Konikbündel werden ihre Diskriminantenorte genauer untersucht und damit Chernklassenabschätzungen für Konikbündel mit relativer Picardzahl 1 über nichtalgebraischen kompakten Kählerflächen hergeleitet. Unter Verwendung dieser Abschätzungen wird die Existenz infinitesimaler Deformationen solcher Konikbündel gezeigt, was einen wichtigen ersten Schritt zum Beweis der algebraischen Approximierbarkeit darstellt. Ein spezieller Typ von Konikbündeln sind die projektivierten Rang-2-Bündel. Die Periodenabbildung verhilft zu einem guten Verständnis der Deformationstheorie solcher Bündel über K3-Flächen und zweidimensionalen Tori. Konkret werden Fortsetzungssätze für Geradenbündel und Rang-2-Bündel bewiesen, die implizieren, dass jedes projektivierte Rang-2-Bündel über einer K3-Fläche oder einem zweidimensionalen Torus algebraisch approximierbar ist. Durch Untersuchung von Aufblasungen solcher Flächen wird dieses Resultat auf projektivierte Rang-2-Bündel über beliebigen kompakten Kählerflächen mit Kodairadimension 0 ausgedehnt. Schließlich wird die zuvor entwickelte Deformationstheorie für Vektorbündel verwendet, um weitere Approximierbarkeitsergebnisse für Konikbündel über elliptischen Flächen und K3-Flächen zu bekommen.
-
An exact column-generation approach for the lot-type design problem
(2012)
-
Sascha Kurz
Miriam Kießling
Jörg Rambau
- We consider a fashion discounter distributing its many branches with
integral multiples from a set of available lot-types. For the problem of
approximating the branch and size dependent demand using those lots
we propose a tailored exact column generation approach assisted by fast
algorithms for intrinsic subproblems, which turns out to be very efficient
on our real-world instances.
-
Beiträge zur Optimalen Steuerung partiell-differential algebraischer Gleichungen
(2012)
-
Armin Rund
- Diese Arbeit liefert Beiträge zur Optimalen Steuerung partiell-differential algebraischer Gleichungen. Insbesondere werden Zustandsbeschränkungen bei der Optimalen Steuerung gewöhnlicher und partieller Differentialgleichungen sowie gekoppelter Systeme untersucht. Die verschiedenen Konzepte dieser Gebiete werden verglichen, übertragen und eingeordnet. Zentrale Ergebnisse sind die Übertragung der notwendigen Bedingungen nach Bryson, Denham und Dreyfus auf elliptische Optimalsteuerungsprobleme mit punktweisen Zustandsbeschränkungen, die Übertragung von Sprungbedingungen und Maßdarstellungen auf ein ODE-PDE beschränktes Optimalsteuerungsproblem mit Zustandsbeschränkungen bei niederdimensionalen aktiven Mengen, sowie die Entwicklung effizienter numerischer Methoden für komplexe Anwendungsprobleme. Die Beiträge dieser Arbeit gliedern sich in vier Kapitel, deren Aspekte jeweils zusammengefasst werden: Zunächst werden die Grundlagen aus der Optimalen Steuerung gewöhnlicher Differentialgleichungen mit Zustandsbeschränkungen wiederholt. Die beiden geläufigen notwendigen Bedingungen nach Jacobson, Lele und Speyer, sowie nach Bryson, Denham und Dreyfus (BDD-Ansatz) werden erläutert und in den Zusammenhang der Optimalen Steuerung partieller Differentialgleichungen gestellt. Dabei wird der Zusammenhang zwischen den Sprungbedingungen und dem Borel-Maß hergestellt. In Kapitel 2 wird der BDD-Ansatz auf ein Optimalsteuerungsproblem einer elliptischen partiellen Differentialgleichung mit punktweisen Zustandsbeschränkungen und verteilten aktiven Mengen übertragen. Die Idee dieses BDD-Ansatzes ist es, die Zustandsbeschränkung auf der aktiven Menge äquivalent in eine Steuerungs-Zustandsbeschränkung oder ggf. eine reine Steuerungsbeschränkung zu transformieren. Dies erlaubt die Herleitung neuer notwendiger Bedingungen. Durch die Transformation der Zustandsbeschränkungen gewinnen die zugehörigen Lagrange-Multiplikatoren an Regularität. Man erhält aus den neuen notwendigen Bedingungen ein Randwertproblem auf verschiedenen Gebieten mit Übergangsbedingungen. Das Interface zwischen den verschiedenen Gebieten stellt eine Optimierungsvariable dar. Eine notwendige Bedingung am Interface wird mit Techniken der Shapeoptimierung hergeleitet. Das Kapitel 3 behandelt Zustandsbeschränkungen bei gemischten ODE-PDE Problemen: Anhand eines zeitabhängigen Anwendungsproblems - des sogenannten Rocketcars - lässt sich eine vollständige Darstellung des Borel-Maßes auf niederdimensionalen aktiven Mengen angeben. In der Folge lassen sich Sprungbedingungen und weitgehende Regularitätsaussagen herleiten. Die explizite Massdarstellung ermöglicht weiterhin die Formulierung als Mehrpunkt-Anfangsrandwertproblem und den Einsatz angepasster Lösungsmethoden. Kapitel 4 widmet sich schließlich einem komplexen Anwendungsproblem eines OC-PDAE: Ein Brennstoffzellenmodell stellt uns vor ein Optimalsteuerungsproblem eines Systems von partiell-differentiell algebraischen Gleichungen. Es werden notwendige Bedingungen hergeleitet und direkte sowie indirekte (adjungierten-basierte) Methoden der Optimalen Steuerung entwickelt und verglichen. Numerische Experimente bestätigen die Effizienz der vorgestellten Methoden. Insbesondere das indirekte Quasi-Newton-Verfahren erlaubt eine zeitadaptive optimale Steuerung der Brennstoffzellenanlage mit hoher Genauigkeit und unter geringer Rechenzeit.
-
Bounds for the minimum oriented diameter
(2008)
-
Sascha Kurz
Martin Lätsch
- We consider the problem of finding an orientation with minimum diameter of a connected bridgeless graph. Fomin et. al. discovered a relation between the minimum oriented diameter an the size of a minimal dominating set. We improve their upper bound.
