Spelling suggestions: "subject:"optimierungsproblem"" "subject:"optimierungsprobleme""
21 |
Network-Design Problems in Graphs and on the Plane / Netzwerk-Design-Probleme in Graphen und auf der EbeneFleszar, Krzysztof January 2018 (has links) (PDF)
A network design problem defines an infinite set whose elements, called instances, describe relationships and network constraints. It asks for an algorithm that, given an instance of this set, designs a network that respects the given constraints and at the same time optimizes some given criterion.
In my thesis, I develop algorithms whose solutions are optimum or close to an optimum value within some guaranteed bound. I also examine the computational complexity of these problems. Problems from two vast areas are considered: graphs and the Euclidean plane.
In the Maximum Edge Disjoint Paths problem, we are given a graph and a subset of vertex pairs that are called terminal pairs. We are asked for a set of paths where the endpoints of each path form a terminal pair. The constraint is that any two paths share at most one inner vertex. The optimization criterion is to maximize the cardinality of the set.
In the hard-capacitated k-Facility Location problem, we are given an integer k and a complete graph where the distances obey a given metric and where each node has two numerical values: a capacity and an opening cost. We are asked for a subset of k nodes, called facilities, and an assignment of all the nodes, called clients, to the facilities. The constraint is that the number of clients assigned to a facility cannot exceed the facility's capacity value. The optimization criterion is to minimize the total cost which consists of the total opening cost of the facilities and the total distance between the clients and the facilities they are assigned to.
In the Stabbing problem, we are given a set of axis-aligned rectangles in the plane. We are asked for a set of horizontal line segments such that, for every rectangle, there is a line segment crossing its left and right edge. The optimization criterion is to minimize the total length of the line segments.
In the k-Colored Non-Crossing Euclidean Steiner Forest problem, we are given an integer k and a finite set of points in the plane where each point has one of k colors. For every color, we are asked for a drawing that connects all the points of the same color. The constraint is that drawings of different colors are not allowed to cross each other. The optimization criterion is to minimize the total length of the drawings.
In the Minimum Rectilinear Polygon for Given Angle Sequence problem, we are given an angle sequence of left (+90°) turns and right (-90°) turns. We are asked for an axis-parallel simple polygon where the angles of the vertices yield the given sequence when walking around the polygon in counter-clockwise manner. The optimization criteria considered are to minimize the perimeter, the area, and the size of the axis-parallel bounding box of the polygon. / Ein Netzwerk-Design-Problem definiert eine unendliche Menge, deren Elemente, als Instanzen bezeichnet, Beziehungen und Beschränkungen in einem Netzwerk beschreiben. Die Lösung eines solchen Problems besteht aus einem Algorithmus, der auf die Eingabe einer beliebigen Instanz dieser Menge ein Netzwerk entwirft, welches die gegebenen Beschränkungen einhält und gleichzeitig ein gegebenes Kriterium optimiert.
In meiner Dissertation habe ich Algorithmen entwickelt, deren Netzwerke stets optimal sind oder nachweisbar nahe am Optimum liegen. Zusätzlich habe ich die Berechnungskomplexität dieser Probleme untersucht. Dabei wurden Probleme aus zwei weiten Gebieten betrachtet: Graphen und der Euklidische Ebene.
Im Maximum-Edge-Disjoint-Paths-Problem besteht die Eingabe aus einem Graphen und einer Teilmenge von Knotenpaaren, die wir mit Terminalpaare bezeichnen. Gesucht ist eine Menge von Pfaden, die Terminalpaare verbinden. Die Beschränkung ist, dass keine zwei Pfade einen gleichen inneren Knoten haben dürfen. Das Optimierungskriterium ist die Maximierung der Kardinalität dieser Menge.
Im Hard-Capacitated-k-Facility-Location-Problem besteht die Eingabe aus einer Ganzzahl k und einem vollständigen Graphen, in welchem die Distanzen einer gegebenen Metrik unterliegen und in welchem jedem Knoten sowohl eine numerische Kapazität als auch ein Eröffnungskostenwert zugeschrieben ist. Gesucht ist eine Teilmenge von k Knoten, Facilities genannt, und eine Zuweisung aller Knoten, Clients genannt, zu den Facilities. Die Beschränkung ist, dass die Anzahl der Clients, die einer Facility zugewiesen sind, nicht deren Kapazität überschreiten darf. Das Optimierungskriterium ist die Minimierung der Gesamtkosten bestehend aus den Gesamteröffnungskosten der Facilities sowie der Gesamtdistanz zwischen den Clients und den ihnen zugewiesenen Facilities.
Im Stabbing-Problem besteht die Eingabe aus einer Menge von achsenparallelen Rechtecken in der Ebene. Gesucht ist eine Menge von
horizontalen Geradenstücken mit der Randbedingung, dass die linke und rechte Seite eines jeden Rechtecks von einem Geradenstück verbunden ist. Das Optimierungskriterium ist die Minimierung der Gesamtlänge aller Geradenstücke.
Im k-Colored-Non-Crossing-Euclidean-Steiner-Forest-Problem besteht die Eingabe aus einer Ganzzahl k und einer endlichen Menge von Punkten in der Ebene, wobei jeder Punkt in einer von k Farben gefärbt ist. Gesucht ist für jede Farbe eine Zeichnung, in welcher alle Punkte der Farbe verbunden sind. Die Beschränkung ist, dass Zeichnungen verschiedener Farben sich nicht kreuzen dürfen. Das Optimierungskriterium ist die Minimierung des Gesamtintenverbrauchs, das heißt, der Gesamtlänge der Zeichnungen.
Im Minimum-Rectilinear-Polygon-for-Given-Angle-Sequence-Problem besteht die Eingabe aus einer Folge von Links- (+90°) und Rechtsabbiegungen (-90°). Gesucht ist ein achsenparalleles Polygon dessen Eckpunkte die gegebene Folge ergeben, wenn man das Polygon gegen den Uhrzeigersinn entlangläuft.
Die Optimierungskriterien sind die Minimierung des Umfangs und der inneren Fläche des Polygons sowie der Größe des notwendigen Zeichenblattes, d.h., des kleinsten Rechteckes, das das Polygon einschließt. / Given points in the plane, connect them using minimum ink. Though the task seems simple, it turns out to be very time consuming. In fact, scientists believe that computers cannot efficiently solve it. So, do we have to resign? This book examines such NP-hard network-design problems, from connectivity problems in graphs to polygonal drawing problems on the plane. First, we observe why it is so hard to optimally solve these problems. Then, we go over to attack them anyway. We develop fast algorithms that find approximate solutions that are very close to the optimal ones. Hence, connecting points with slightly more ink is not hard.
|
22 |
Complexity and Approximation of the Rectilinear Steiner Tree ProblemMussafi, Noor Saif Muhammad 05 August 2009 (has links)
Given a finite set K of terminals in the plane. A
rectilinear Steiner minimum tree for K (RST) is
a tree which interconnects among these terminals
using only horizontal and vertical lines of shortest
possible length containing Steiner point. We show the
complexity of RST i.e. belongs to NP-complete.
Moreover we present an approximative method of
determining the solution of RST problem proposed by Sanjeev Arora
in 1996, Arora's Approximation Scheme. This algorithm
has time complexity polynomial in the number of
terminals for a fixed performance ratio 1 + Epsilon.
|
23 |
Optimierung hochpoliger Dauermagnetmotoren unter Verwendung der Finiten Elemente Methode und der Evolutionsstrategie / Design Optimization of Permanent Magnet Motors by Evolution Strategies and Finite Element AnalysisBochnia, Dirk 19 September 2002 (has links) (PDF)
The power and force density of electric motors becomes higher and higher and it is very important to design most optimal machines. Conventional methods dont reach this aim in any case. A new approach is presented combining Evolutionary Strategies and Finite Element Analysis to obtain reliable results. / Die Anforderungen an elektrische Antriebe sind sehr hoch. Nur optimal konstruierte Maschinen können ihnen genügen. Es wird ein Instrumentarium vorgestellt, welches eine rechnergestützte automatische Optimierung des magnetischen Kreises der elektrischen Maschine gestattet. Als Modellierungsgrundlage wird die Finite-Elemente-Methode verwendet. Die Optimierung erfolgt mit der Evolutionsstrategie.
Aufgrund des hohen Rechenaufwandes der FEM wird insbesondere darauf eingegangen, ein Modell zu schaffen, dass möglichst viel Information bei hoher Genauigkeit und geringstem numerischen Aufwand liefert. Entsprechende Möglichkeiten der Simulation magnetischer und thermischer Felder mit der FEM werden besprochen. Außerdem wird ein Verfahren vorgestellt, welches die Ermittlung der magnetischen Verluste ohne transienter Feldberechnungen erlaubt.
Die Modellierung wird speziell am Beispiel eines hochpoligen permanenterregten Synchronmotors in Außenläuferbauweise erläutert. Die Ergebnisse der Simulation werden mit Messungen verglichen. Weiterhin werden die Ergebnisse verschiedener konkreter Optimierungsläufe vorgestellt.
|
24 |
New insights into conjugate dualityGrad, Sorin - Mihai 19 July 2006 (has links) (PDF)
With this thesis we bring some new results and improve some
existing ones in conjugate duality and some of the areas it is
applied in.
First we recall the way Lagrange, Fenchel and Fenchel - Lagrange
dual problems to a given primal optimization problem can be
obtained via perturbations and we present some connections between
them. For the Fenchel - Lagrange dual problem we prove strong
duality under more general conditions than known so far, while for
the Fenchel duality we show that the convexity assumptions on the
functions involved can be weakened without altering the
conclusion. In order to prove the latter we prove also that some
formulae concerning conjugate functions given so far only for
convex functions hold also for almost convex, respectively nearly
convex functions.
After proving that the generalized geometric dual problem can be
obtained via perturbations, we show that the geometric duality is
a special case of the Fenchel - Lagrange duality and the strong
duality can be obtained under weaker conditions than stated in the
existing literature. For various problems treated in the
literature via geometric duality we show that Fenchel - Lagrange
duality is easier to apply, bringing moreover strong duality and
optimality conditions under weaker assumptions.
The results presented so far are applied also in convex composite
optimization and entropy optimization. For the composed convex
cone - constrained optimization problem we give strong duality and
the related optimality conditions, then we apply these when
showing that the formula of the conjugate of the precomposition
with a proper convex K - increasing function of a K - convex
function on some n - dimensional non - empty convex set X, where
K is a k - dimensional non - empty closed convex cone, holds under
weaker conditions than known so far. Another field were we apply
these results is vector optimization, where we provide a general
duality framework based on a more general scalarization that
includes as special cases and improves some previous results in
the literature. Concerning entropy optimization, we treat first
via duality a problem having an entropy - like objective function,
from which arise as special cases some problems found in the
literature on entropy optimization. Finally, an application of
entropy optimization into text classification is presented.
|
25 |
Identification of material parameters in mechanical modelsMeyer, Marcus 04 June 2010 (has links) (PDF)
Die Dissertation beschäftigt sich mit
Parameteridentifikationsproblemen, wie sie häufig in
Fragestellungen der Festkörpermechanik zu finden sind. Hierbei
betrachten wir die Identifikation von Materialparametern -- die
typischerweise die Eigenschaften der zugrundeliegenden
Materialien repräsentieren -- aus gemessenen Verformungen oder
Belastungen eines Testkörpers. In mathematischem Sinne
entspricht dies der Lösung von Identifikationsproblemen, die
eine spezielle Klasse von inversen Problemen bilden.
Der Inhalt der Dissertation ist folgendermaßen gegliedert. Nach
dem einführenden Abschnitt 1 wird in Abschnitt 2 ein Überblick
von Optimierungs- und Regularisierungsverfahren zur stabilen
Lösung nichtlinearer inverser Probleme diskutiert. In Abschnitt
3 betrachten wir die Identifikation von skalaren und stückweise
konstanten Parametern in linearen elliptischen
Differentialgleichungen. Hierbei werden zwei Testprobleme
erörtert, die Identifikation von Diffusions- und
Reaktionsparameter in einer allgemeinen elliptischen
Differentialgleichung und die Identifikation der
Lame-Konstanten in einem Modell der linearisierten Elastizität.
Die zugrunde liegenden PDE-Modelle und Lösungszugänge werden
erläutert. Insbesondere betrachten wir hier Newton-artige
Algorithmen, Gradientenmethoden, Multi-Parameter
Regularisierung and den evolutionären Algorithmus CMAES.
Abschließend werden Ergebnisse einer numerischen Studie
präsentiert. Im Abschnitt 4 konzentrieren wir uns auf die
Identifikation von verteilten Parametern in hyperelastischen
Materialmodellen. Das nichtlineare Elastizitätsproblem wird
detailiert erläutert und verschiedene Materialmodelle werden
diskutiert (linear elastisches St.-Venant-Kirchhoff Material
und nichtlineare Neo-Hooke, Mooney-Rivlin und Modified-Fung
Materialien. Zur Lösung des resultierenden
Parameteridentifikationsproblems werden Lösungsansätze aus der
optimalen Steuerung in Form eines Newton-Lagrange SQP
Algorithmus verwendet. Die Resultate einer numerischen Studie
werden präsentiert, basierend auf einem zweidimensionales
Testproblem mit einer sogenannten Cook-Mebran. Abschließend
wird im Abschnitt 5 die Verwendung adaptiver FEM für die Lösung
von Parameteridentifikationsproblems kurz erörtert. / The dissertation is focussed on parameter identification
problems arising in the context of structural mechanics. At
this, we consider the identification of material parameters -
which typically represent the properties of an underlying
material - from given measured displacements and forces of a
loaded test body. In mathematical terms such problems denote
identification problems as a special case of general inverse
problems.
The dissertation is organized as follows. After the
introductive section 1, section 2 is devoted to a survey of
optimization and regularization methods for the stable solution
of nonlinear inverse problems. In section 3 we consider the
identification of scalar and piecewise constant parameters in
linear elliptic differential equations and examine two test
problems, namely the identification of diffusion and reaction
parameters in a generalized linear elliptic differential
equation of second order and the identification of the Lame
constants in the linearized elasticity model. The underlying
PDE models are introduced and solution approaches are discussed
in detail. At this, we consider Newton-type algorithms,
gradient methods, multi-parameter regularization, and the
evolutionary algorithm CMAES. Consequently, numerical studies
for a two-dimensional test problem are presented. In section 4
we point out the identification of distributed material
parameters in hyperelastic deformation models. The nonlinear
elasticity boundary value problem for large deformations is
introduced. We discuss several material laws for linear elastic
(St.-Venant-Kirchhoff) materials and nonlinear Neo-Hooke,
Mooney-Rivlin, and Modified-Fung materials. For the solution of
the corresponding parameter identification problem, we focus on
an optimal control solution approach and introduce a
regularized Newton-Lagrange SQP method. The Newton-Lagrange
algorithm is demonstrated within a numerical study. Therefore,
a simplified two-dimensional Cook membrane test problem is
solved. Additionally, in section 5 the application of adaptive
methods for the solution of parameter identification problems
is discussed briefly.
|
26 |
Efficient checking of polynomials and proofs and the hardness of approximation problems /Sudan, Madhu. January 1900 (has links)
Based on the author's Ph. D. thesis, University of California, Berkeley, 1993. / Includes bibliographical references (p. [73]-78) and index. Also issued online.
|
27 |
Zeitbeschränkte Ablaufplanung mit Neuronalen Netzen für Geclusterte VLIW-ProzessorenScholz, Sebastian, Schölzel, Mario, Bachmann, Peter 11 June 2007 (has links)
Es wird ein Ansatz zur zeitbeschränkten
Ablaufplanung für VLIW-Prozessoren
mit neuronalen Netzen vorgestellt. Bestehende Arbeiten
werden dahingehend erweitert, dass der Datenpfad
des Prozessors über heterogene funktionale
Einheiten verfügen und geclustert sein darf. Es werden
zwei Varianten zur Lösung des Problems angegeben,
deren Qualität mit einem heuristischen
Ansatz verglichen wird und Schlussfolgerungen bezüglich
der Nutzbarkeit neuronaler Netze gezogen.
|
28 |
Complexity and Approximation of the Rectilinear Steiner Tree ProblemMussafi, Noor Saif Muhammad 21 July 2009 (has links)
Given a finite set K of terminals in the plane. A
rectilinear Steiner minimum tree for K (RST) is
a tree which interconnects among these terminals
using only horizontal and vertical lines of shortest
possible length containing Steiner point. We show the
complexity of RST i.e. belongs to NP-complete.
Moreover we present an approximative method of
determining the solution of RST problem proposed by Sanjeev Arora
in 1996, Arora's Approximation Scheme. This algorithm
has time complexity polynomial in the number of
terminals for a fixed performance ratio 1 + Epsilon.
|
29 |
A Models@run.time Approach for Multi-objective Self-optimizing SoftwareGötz, Sebastian, Kühn, Thomas, Piechnick, Christian, Püschel, Georg, Aßmann, Uwe 05 July 2021 (has links)
This paper presents an approach to operate multi-objective self-optimizing software systems based on the models@run.time paradigm. In contrast to existing approaches, which are usually specific to a single or selected set of objectives (e.g., performance and/or reliability), the presented approach is generic in that it allows the software architect to model the relevant concerns of interest to self-optimization. At runtime, these models are interpreted and used to generate optimization problems. To evaluate the applicability of the approach, a scalability analysis is provided, showing the approach’s feasibility for at least two objectives.
|
30 |
Analyse, Modellierung und Verfahren zur Kompensation von CDN-bedingten Verkehrslastverschiebungen in ISP-NetzenWindisch, Gerd 17 March 2017 (has links) (PDF)
Ein großer Anteil des Datenverkehrs in „Internet Service Provider“ (ISP)-Netzen wird heutzutage von „Content Delivery Networks“ (CDNs) verursacht. Betreiber von CDNs verwenden Lastverteilungsmechanismen um die Auslastung ihrer CDN-Infrastruktur zu vergleichmäßigen (Load Balancing). Dies geschieht ohne Abstimmung mit den ISP-Betreibern. Es können daher große Verkehrslastverschiebungen sowohl innerhalb eines ISP-Netzes, als auch auf den Verbindungsleitungen zwischen ISP-Netz und CDNs auftreten.
In der vorliegenden Arbeit wird untersucht, welche nicht-kooperativen Möglichkeiten ein ISP hat, um Verkehrslastverschiebungen, welche durch Lastverteilungsmechanismen innerhalb eines CDNs verursacht werden, entgegenzuwirken bzw. abzumildern. Die Grundlage für diese Untersuchung bildet die Analyse des Serverauswahlverhaltens des YouTube-CDNs. Hierzu ist ein aktives Messverfahren entwickelt worden, um das räumliche und zeitliche Verhalten der YouTube-Serverauswahl bestimmen zu können. In zwei Messstudien wird die Serverauswahl in deutschen und europäischen ISP-Netzen untersucht. Auf Basis dieser Studien wird ein Verkehrsmodell entwickelt, welches die durch Änderungen der YouTube-Serverauswahl verursachten Verkehrslastverschiebungen abbildet. Das Verkehrsmodell wiederum bildet die Grundlage für die Bestimmung optimaler Routen im ISP-Netz, welche hohe Robustheit gegenüber CDN-bedingte Verkehrslastverschiebungen aufweisen (Alpha-robuste Routingoptimierung). Für die Lösung des robusten Routing-Optimierungsproblems wird ein iteratives Verfahren entwickelt sowie eine kompakte Reformulierung vorgestellt. Die Leistungsfähigkeit des Alpha-robusten Routings wird anhand von drei Beispielnetztopologien untersucht. Das neue Verfahren wird mit alternativen robusten Routingverfahren und einem nicht-robusten Verfahren verglichen. Neben der robusten Routingoptimierung werden in der Arbeit drei weitere Ideen für nicht-kooperative Methoden vorgestellt (BGP-, IP-Präix- und DNS-basierte Methode), um CDN-bedingten Verkehrslastverschiebungen entgegenzuwirken.
|
Page generated in 0.2834 seconds