Diplomarbeiten

Back to the top

Ganzzahlige und gemischt-ganzzahlige Optimierung

M. Deppermann: Die kombinatorischen Verfahren von Balas - Modifikationen und Erweiterungen auf Probleme mit quadratischer Zielfunktion. April 1984.
The treatise is based on the combinatorial algorithms of Balas. A lot of suggestions of improvement (Glover, Petersen, Geoffrion und Fleischmann) are used to develop efficient algorithms for solving zero-one linear programming problems. Finally the procedures are generalized for solving problems with quadratic objective function. A special algorithm is numerically tested and compared with an algorithm of Laughhunn.

R. Müller: Das Verfahren von Benders: Modifikation, Erweiterungen und Vergleiche mit Standardverfahren der gemischt-ganzzahligen Optimierung. Dezember 1985.

F. Moneta: Die Verwendung von Schnittebenen nach Balas und Burdet in der ganzzahligen Optimierung. April 1987.
The treatise is mainly based on publications of Balas and Burdet which deal with the construction of cutting-planes by geometric methods. Different algorithms are presented which are compared with the classical Gomory cutting-plane methods.

D. Schnotale: Additive Verfahren in der ganzzahligen und gemischt-ganz- zahligen linearen Optimierung. Juni 1988.
An enumeration algorithm is presented for solving (mixed-) integer linear programming problems. It comprises methods of Land and Doig, Balas and Driebeek to a common procedure. The qualitity of the algorithm is confirmed by computational tests on a large scale. The algorithm is based on results contained in a preprint of Beisel/Mendel.

J. Tennie: Das Verfahren von Driebeek - Darstellung, Modifikation und Erweiterung des Verfahrens. Mai 1989.
Ideas of Driebeek are used to develop a new algorithm for solving mixed-integer linear programming problems. The algorithm is numerically tested by solving many problems.

B. Schmadtke: Kapazitive Enumerationsverfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Juni 1989.
The treatise deals with a modification of the the above-mentioned algorithm presented by Schnotale. The enumeration procedure and the bounding criteria are altered. The formulation of the algorithm is restricted to solve only all-integer linear programming problems. Computational experience is obtained by solving a lot of numerical examples.

von Engelmann: Darstellung und Realisierung eines enumerativen Schnittebenenverfahrens zur Lösung wesentlich- und gemischt-ganzzahliger linearer Optimierungsaufgaben. 1992.
A hybrid algorithm which combines cutting-plane methods with a branch-and-bound procedure is presented. It is an improvement of an algorithm developed by Habenicht in 1976. A different enumeration prodecue is used and the algorithm is generalized for solving mixed-integer problems. Large-scale tests are carried out.

M. Berg: Branch-and-Bound Techniken mit Inneren Punkte Methoden. Oktober 1995.

H. Klug: Die Cross-Dekomposition zur Lösung des Facility Location Problems. Juni 1998.

Back to the top

Innere-Punkte-Methoden der linearen Optimierung

W.Wurm: Numerische Lösungsalgorithmen für das Minimumproblem im Verfahren von Karmarkar. Februar 1987

B. Hoffmann: Lösen eines linearen Problems ausgehend von einem unzulässigen ``Warm-Start'' mit Hilfe einer Potentialfunktion. Dezember 1994.
In practice, often an infeasible starting point for a linear programming problem is known which is `` close'' to the set of optimal solutions. This may occur, if the optimal solution of a problem is already computed but some data of the problem are altered afterwards. The treatise presents an interior-point algorithm which tries to take advantage of this special situation. It is shown that the practical performance and the complexity of the algorithm depends on the fact how close the starting point is to the set of LP feasible and optimal solutions. (For this purpose, measures of infeasibity and nonoptimality are given.) The treatise is based on papers of R. M. Freund.

A.Albertz: Historische und numerische Einordnung zweier projektiver Innerer-Punkt-Methoden. Dezember 1994

P. Schneider: Affine-Scaling Algorithmen mit Zentrierung. Januar 1995.
The recent remarkable developments of interior point algorithms began in 1984 with Karmarkar's polynomial-time interior point algorithm for linear programs. Since then, numerous interior point algorithms have been proposed. According to their main mathematical tools, these algorithms are devided into the following classes: potential-reduction algorithms, path-following algorithms, affine-scaling algorithms, barrier-function methods. The treatise represents an affine-scaling algorithms which also uses centering directions. It is mainly based on a technical report of Barnes, Chopra and Jensen. The algorithm is tested by means of a lot of numerical examples.

R. Arndt: Das Homotopieprinzip bei Innere Punkte Methoden über direkte Parametrisierung des KKT-Systems. Mai 1995.

R. Küll: Primal-duale pfadorientierte Innere-Punkte-Verfahren mit Prädiktor-Korrektor-Suchrichtungen zur Lösung linearer Optimierungsaufgaben. Juni 1995.
The treatise presents a special class of path-following interior-point-algorithms which has been developped by Mizuno,Todd and Ye. The algorithms use a predictor-corrector search direction. They are modified with the aim of using a simplified search direction. The convergence analysis of the algorithms is carefully drawn up. The algorithms are geometrically described, implemented and numerically tested with problems of the Netlib Testset.

C. Brechtmann: Primal-duale Affine-Scaling Algorithmen zur Lösung linearer Optimierungsaufgaben. Juni 1995.
The treatise presents primal-dual affine-scaling algorithms, a ``classical'' one which stems from Monteiro, Adler and Resende (1990) and a new one which is based on a paper of Jansen, Roos and Telaky (1993). Both algorithms are theoretically compared. They both are implemented, they are numerically tested in comparison with each other.

J. König: Zur Big-M-Problematik bei Innere-Punkte-Verfahren. Januar 1996.
Interior Point Methods (IPM) need a suitable interior starting point. However, such a point is usually not available. Therefore the given problem is modified by using a Big-$M$ setting to overcome this drawback. The treatise presents primal, dual and primal-dual concepts for using Big-M procedures (with fixed and non-fixed M). It is based on papers of Andersen, Kojima et al. and Lustig and discusses the difficulties which arise when the procedures are applied to numerical problems.

F. Krummenauer: Verschiedene Ansätze für die Herleitung der Karmarkar-Abstiegsrichtung. Mai 1996.

A. Hollstein: Updating Schemes in einem modifizierten Karmarkar-Verfahren. August 1996.
The treatise deals with updating schemes in a special potential reduction linear programming algorithm of Kojima, Mizuno and Yoshise. It is mainly based on papers of Ye and Bosch and Anstreicher. A simple safeguard condition is developped to control the number of updates incurred on combined primal-dual steps. The algorithms are tested with the Netlib Testset.

Y. Guo-Preuße: Innere-Punkte-Verfahren mit aus Barrieretermen abgeleiteten Suchrichtungen. Oktober 1996.

A. Schütz: Das Build-Up- und Build-Down-Verfahren als Möglichkeit zur Reduzierung des Rechenaufwandes bei dualen Innere-Punkte-Verfahren. Oktober 1996.
One drawback to all interior point methods is the great computational effort required in each iteration. The search direction is obtained by solving a linear system with a matrix of the typ $AD^{-2}A^T$, where $D$ is a positive diagonal matrix depending on the current iterate. Therefore, working with a subset of the dual constraints rather than the full system, would save a great deal of computations. The first such an attempt to save computations is the so-called ``column deletion'' method, proposed by Ye. In his approach, a criterion for detecting non-binding constraints is derived. If a constraint is detected to be non-binding in the optimal set, it is removed from the system, which becomes smaller. So the computational effort for computing the search direction is reduced. The second attempt to save computations is the ``build-up'' or ``column generation''. The treatise is an introduction into this subject. It is based on papers of Ye and den Hertog and al. Different algorithms are numerically tested.

A. Saage: Auf Todds Potentialfunktion basierende Innere-Punkte-Verfahren. Februar 1997.

G. Moussis: Ein Vergleich zwischen Methoden mit logarithmischer Barrierefunktion und solchen mit Potentialfunktion. Juli 1997.

M. Noppen: Eine superlinear konvergente Variante des primalen Affine Scaling Algorithmus. Juli 1997.

C. Weiß: Primale Affine Scaling Verfahren mit Zentrierung. Juni 1998.

 Back to the top

Äußere-Punkte-Methoden der linearen Optimierung

J. Korzak: Primal-duale pfadfolgende Äußere-Punkte-Verfahren zur Lösung linearer Optimierungsaufgaben. Juni 1994
Since 1991, several primal-dual exterior point algorithms for linear programming have been published. The treatise takes up this subject. It presents the fundamental primal-dual path-following exterior-point-algorithm of Kojima, Megiddo and Mizuno, two polynomially convergent variants of Mizuno and a modification of Mehrotra. The practical performance of the algorithms is always tested by solving the problems of the Netlib Testset.

F. Straßmann: Primal-duale potential-reduzierende Äußere-Punkte-Verfahren zur Lösung linearer Optimierungsaufgaben. Juni 1995.
On the field of exterior point methods for linear programming, three essential classes of algorithms have been developped: path-following methods, potential-reduction algorithms and affine-scaling procedures. The treatise deals with potential-reduction methods. Based on a fundamental interior-point algorithm of Gonzaga, an exterior potential-reduction method, developped by Kojima, Mizuno and Todd in 1992, is presented and numerically tested by means of the Netlib Testset.

J. Korzak: Primal-duale pfadfolgende inexakte Äußere-Punkte-Verfahren zur Lösung linearer Optimierungsaufgaben. April 1997.
The above-mentioned exterior-point-algorithms are designed for computing the search direction accurately. The dissertation presents the convergence analysis for a class of inexakt exterior-point methods. The search direction computed at each iteration point need not to be solved to high accurancy. More precisely, the system of linear equations which discribes the search direction is only solved approximately. The algorithms of Kojima, Megiddo and Mizuno and a modification of Mehrotra are generalized in such a way that inexact search directions can be used. It is shown that the main algorithms are polynomially convergent.

A. Tsagoudis: Potentialreduzierende zentrierende primal-duale Äußere-Punkte-Verfahren zur Lösung linearer Optimierungsaufgaben. August 1997.

J. Johenneken: Eine pfadfolgende Variante Äußerer Punkte-Verfahren. Februar 1998.

J. Depner: Ein inexaktes Äußere-Punkte-Verfahren mit dynamisch-zentrierender Suchrichtung zur Lösung linearer Optimierungsaufgaben. April 1998.
The treatise is mainly based on two papers of Mizuno, Freund and Jarre. On the basis of the fundamental exterior-point method of Kojima, Megiddo and Mizuno, Depner develops and describes the inexact algorithm of Mizuno et al. He carefully draws up the proves. The algorithm is numerically tested with the problems of the Netlib Testset. The results are compared with those which Korzak has obtained by computations using his inexact algorithm.

M. Jansen: Analyse zulässiger und unzulässiger Pfade in der linearen Optimierung und Konstruktion von Verfahren, die sich an solchen Pfaden orientieren. Juni 1998.
An important class of interior- and exterior-point methods consists of path-following algorithms. The construction of these algorithms is based on the central path of a primal-dual pair of linear programms. This path runs through the feasible region and leads to the optimal face of the problem. But it exists if and only if the primal-dual feasible region has a strictly feasible solution. Stoer proposed to define infeasible paths which exist on weaker assumptions. The treatise deals with special feasible and infeasible paths and presents algorithms which are orientated according to such a path. The algorithms are numerically tested on the Netlib Testset.

Back to the top

Lineare Komplementaritätsprobleme

R. Aubart: Das lineare Komplementaritätsproblem und ein superlinearer primal-dualer Affine-Scaling-Algorithmus. Februar 1997.
First, the treatise states an introduction into linear complementary problems. The main classes of such problems with some important properties are represented. Then a class of superlinear primal-dual affine-scaling algorithms based on papers of Monteiro/Wright is drawn up. A special variant of these algorithms is implemented and numerically tested
Back to the top

Optimierung in Graphen oder mit graphentheoretischen Methoden

A. Kirchgaesser: Zur Lösung eines Bestellproblems mit beliebigen, stückweise linearen stetigen Kostenfunktionen. März 1983.

Trzaska

E. Nebgen: Ein neuer Nichtsimplex-Algorithmus zur Flußminimierung

H. Gößl: Verfahren zulässiger Abstiegsrichtungen zur Lösung verallgemeinerter Flußprobleme. März 1986

V. Schmidt: Darstellung und numerischer Vergleich von Methoden zur Lösung eines verallgemeinerten Kostenplanungsproblems. Mai 1987

M. Meis: Untersuchung der Partitioning Shortest Path-Algorithmen zur Bestimmung kürzester Wege in Graphen. Juli 1992.

M. Treder: Negative Kreise in Netzen. 1993.

B. Luter: Algorithmus zur Berechnung eines kostenminimalen Flusses auf kürzesten Wegen im gerichteten Graphen. 1993.

S. Wellmann: Primal-duale und duale Verfahren zur Lösung von Flußminimierungsaufgaben in gerichteten Graphen. Dezember 1993.

B. Klein: Entwicklung und Realisation eines Partitionsverfahrens zur Lösung von linearen Mehrgüterflußproblemen. August 1994.

A. Blei: Herleitung dreier Algorithmen zur Reduzierung der Anzahl der Nicht-Null-"Elemente einer spärlich besetzten Matrix unter Anwendung graphentheoretischer Methoden. November 1994.

B. Pütz: Darstellung und Realisierung eines Verfahrens zur Lösung des 'Allgemeinen Flußproblems'. August 1994.

A. Weinberg: Zur Lösung des symmetrischen Travelling Salesman Problems mit Linearer Programmierung. Mai 1995.

B. Kurschilgen: Lösung von unkapazitierten und kapazitierten Flußproblemen mit Hilfe des dualen Affine-Scaling-Algorithmus und des Simplexverfahrens in Graphen. Dezember 1995.
The treatise deals with classical and new algorithms for solving minimum cost flows on capacitated and uncapacitated networks. The simplex algorithm for networks and variants of the dual affine-scaling algorithm based on papers of Resende/Veiga are presented. The practical performance of both kinds of algorithms is compared by solving a lot of numerical problems generated by Netgen.

K. Lauschke: Ein stark polynomialer skalierender Netz-Auktions-Algorithmus zur Flußminimierung in Graphen. März 1997.

B. Vedder gen. Stute: Stark polynomiale kreis- oder schnittauflösende Algorithmen zur Flußminimierung in Graphen. März 1997.

S. Knupp: Polynomiale RHS-Scaling Algorithmen zur Lösung von Flußminimierungsproblemen in gerichteten Netzen. April 1997.

S. Pütz: Preflow-Push Algorithmen Die stärksten Verfahren zur Lösung des Maximalen Flußproblems im Vergleich. Juli 1998.

Back to the top

Allgemeine lineare Optimierung

J.Voß: Vergleichende Untersuchungen über direkte und indirekte Dekompositionsverfahren der linearen Optimierung. Juni 1984.

R. Premk: Eine heuristische Vorphase für das Simplexverfahren. Juli 1988.

O.Thomas: Primale Dekomposition mit integrierter Produktform der Inversen. August 1990.

B. Nuyken: Untersuchungen zu einem Algorithmus für lineare Optimierungsaufgaben von P. Kosmol. Januar 1990.

V. Hannemann: Die Gravitationsmethode: Eine Innere-Punkte-Methode zur Lösung linearer Optimierungsaufgaben. September 1994.

S. Graf: Revidierte Simplexverfahren mit Techniken zur Aufdatierung der lBasismatrix nach Bartels/Golup,Forrest/Tomlin und Fletcher/Matthews. Juli 1997.

Back to the top

Methoden der Nichtlinearen Optimierung

N. Dietsch: Der Algorithmus von Chatschijan: Modifikationen, numerische Erfahrungen und Anwendungen auf lineare und nichtlineare Optimierungsaufgaben. 1985.

D.Studener: Optimierung von Membranformen im Hinblick auf das Bruchverhalten einer rotationssymmetrischen Betonplatte. 1988.

T. Kriese: Das Nearest Point Problem - Theorie, Algorithmen und numerische Auswertung. November 1994.

M. Forster: Schnittebenenverfahren zur Lösung konvexer Optimierungsaufgaben und deren Implementierung mit Innere-Punkte-Methoden. März 1995.

C. Antonin: Aspekte des Line Search in Newton- Verfahren zur Lösung von nichtlinearen Gleichungssystemen. August 1995.

S.Frings: Pfadfolgende Algorithmen zur Lösung konvexer quadratischer Optimierungsaufgaben und eine Anwendung auf das Portfolio-Selection-Modell. Januar 1996.

R. Caplan: Klassische und neuere Schnittebenenverfahren der konvexen Optimierung. Mai 1998.

S. Blind: Methoden der sequentiellen Minimierung mit Penalty-Funktionen zur Lösung nichtlinearer Optimierungsaufgaben. Juni 1998.