Investigating Distributed Approaches for Solving Discrete, Multistage Optimization Problems

Mémoire (de fin d'études) , 2004 , 83 Pages , Note: 1,3

Informatique - Informatique Appliquée à la Gestion

Im Mittelpunkt dieser Diplomarbeit steht die Optimierung mehrstuger Probleme. Hinführend werden zunächst die theoretischen Hintergründe der Optimierung erläutert. Im Fokus der Erläuterungen steht die Unterscheidung der simulationsbasierten und der verteilten Optimierung. Simulationsbasierte Optimierungen lassen keine algebraische Berechnung von Zielfunktionswerten zu. Diese erfordern besondere Lösungsstrategien, da bei der Auswertung keine Ableitungsinformationen entstehen. Des Weiteren beschäftigt sich diese Diplomarbeit mit der Untersuchung und Implementierung von Lösungsstrategien für die Auswertung der Problemklasse der ableitungsfreien oder auch direkten Suchverfahren. Weiterhin wird auf die spezielle Problemstellung der Mehrstugkeit eingegangen, bei welcher nicht nur Zielfunktionswerte, sondern auch eine optimale Stufenzahl ermittelt werden müssen. Dabei sind die Ergebnisse der nächsten Stufe stets abhängig von denen der Stufen davor. Die bei der Auswertung von Punkten erforderliche hohe Rechenleistung bei der simulationsbasierten Optimierung lässt Einprozessorsysteme während der Optimierung schnell an zeitliche Grenzen stoÿen. Aus diesem Grund werden in der vorliegenden Arbeit zwei Algorithmen vorgestellt und implementiert, die vollständig verteilt rechnen und skalierbar sind. Kapitel 5 beschäftigt sich mit Scatter Search, einem etablierten Verfahren zur Lösung nichtlinearer, ableitungsfreier Probleme. Im Zuge dieser Arbeit wurde das Verfahren zur Lösung zweier Testprobleme eingesetzt, die Ergebnisse nden sich in Kapitel 6. [...]

Inhaltsverzeichnis

• Introduction.
• Optimization
  • Introduction
  • Simulation-Based Optimization
    • Background
    • Applications
  • Parallel and Distributed Computing
    • Background
    • Applications
  • Grid Computing..
    • Background
    • Applications.
    • Future Prospects
  • Performance Evaluation
    • Speedup
    • Efficiency
    • Scalability
• Discrete Multistage Processes
  • Introduction
  • Discrete Multistage Manufacturing Processes
  • Challenges
• Solution Approaches
  • Introduction
  • Simplex Approaches
  • Evolutionary Approaches.
  • Mixed Integer Approaches
• Implementation of Two Algorithms for Solving Multistage Problems .
  • Introduction.
  • Implementation Structure,
  • Scatter Search.
    • Basic Heuristic
    • Parallelization
    • Overview
    • Method Description
    • Performance Evaluation
  • Branch and Bound
    • Introduction
    • Basic Design.
    • Basic Heuristic
    • Parallelization
    • Overview
    • Method Description
    • Performance Evaluation
• Applications to the Approaches
  • Introduction
  • Test Problems
    • N-Dimensional Rosenbrock Problem .
    • Multistage Test Problem
  • Test Results .
    • Scatter Search
    • Branch and Bound
    • Grid Environment
• Summary and Future Work

Zielsetzung und Themenschwerpunkte

This diploma thesis focuses on the optimization of multistage problems. It begins by explaining the theoretical background of optimization, particularly the distinction between simulation-based and distributed optimization. Simulation-based optimization does not allow for algebraic calculation of objective function values, requiring special solution strategies due to the lack of derivative information. The thesis investigates and implements solution strategies for evaluating the problem class of derivative-free or direct search methods. It also addresses the specific problem of multistage optimization, where not only objective function values but also an optimal number of stages must be determined. The results of the next stage are always dependent on those of the previous stages. The high computational power required for evaluating points in simulation-based optimization quickly leads single-processor systems to time limits during optimization. Therefore, this work presents and implements two algorithms that are fully distributed and scalable.

• Optimization of multistage problems
• Simulation-based optimization
• Distributed optimization
• Derivative-free or direct search methods
• Implementation of scalable algorithms for multistage optimization

Zusammenfassung der Kapitel

Chapter 2 provides a comprehensive overview of optimization, focusing on simulation-based optimization and its applications. It also delves into parallel and distributed computing, including grid computing and its potential for future optimization problems. Chapter 3 introduces the concept of discrete multistage processes, highlighting their challenges and applications in manufacturing. Chapter 4 explores various solution approaches for multistage problems, including simplex, evolutionary, and mixed integer approaches. Chapter 5 focuses on the implementation of two algorithms for solving multistage problems: Scatter Search and Branch and Bound. Both algorithms are designed to be fully distributed and scalable, leveraging the power of parallel and distributed computing. Chapter 6 presents the application of these algorithms to two test problems: the N-Dimensional Rosenbrock problem and a multistage test problem. The chapter analyzes the performance of the algorithms and discusses their effectiveness in solving multistage optimization problems. Finally, Chapter 7 summarizes the findings of the thesis and outlines potential directions for future research.

Schlüsselwörter

The keywords and focus themes of the text include multistage optimization, simulation-based optimization, distributed optimization, derivative-free optimization, Scatter Search, Branch and Bound, parallel computing, grid computing, and multistage manufacturing processes. The thesis explores the challenges and opportunities of solving multistage optimization problems using distributed approaches, highlighting the potential of parallel and grid computing for improving efficiency and scalability.

• Université: University of Siegen
• Note: 1,3
• Auteur: Christian Kutsch (Auteur)
• Année de publication: 2004
• Pages: 83
• N° de catalogue: V109467
• ISBN (ebook): 9783640076482
• ISBN (Livre): 9783656244813
• Langue: anglais
• mots-clé: Investigating, Distributed, Approaches, Solving, Discrete, Multistage, Optimization, Problems, Scatter Search