Investigating Distributed Approaches for Solving Discrete, Multistage Optimization Problems

Diploma Thesis , 2004 , 83 Pages , Grade: 1,3

Computer Science - Commercial Information Technology

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 (Table of Contents)

• 1. Introduction
• 2. Optimization
  • 2.1 Introduction
  • 2.2 Simulation-Based Optimization
    • 2.2.1 Background
    • 2.2.2 Applications
  • 2.3 Parallel and Distributed Computing
    • 2.3.1 Background
    • 2.3.2 Applications
  • 2.4 Grid Computing
    • 2.4.1 Background
    • 2.4.2 Applications
    • 2.4.3 Future Prospects
  • 2.5 Performance Evaluation
    • 2.5.1 Speedup
    • 2.5.2 Efficiency
    • 2.5.3 Scalability
• 3. Discrete Multistage Processes
  • 3.1 Introduction
  • 3.2 Discrete Multistage Manufacturing Processes
  • 3.3 Challenges
• 4. Solution Approaches
  • 4.1 Introduction
  • 4.2 Simplex Approaches
  • 4.3 Evolutionary Approaches
  • 4.4 Mixed Integer Approaches
• 5. Implementation of Two Algorithms for Solving Multistage Problems
  • 5.1 Introduction
  • 5.2 Implementation Structure
  • 5.3 Scatter Search
    • 5.3.1 Basic Heuristic
    • 5.3.2 Parallelization
    • 5.3.3 Overview
    • 5.3.4 Method Description
    • 5.3.5 Performance Evaluation
  • 5.4 Branch and Bound
    • 5.4.1 Introduction
    • 5.4.2 Basic Design
    • 5.4.3 Basic Heuristic
    • 5.4.4 Parallelization
    • 5.4.5 Overview
    • 5.4.6 Method Description
    • 5.4.7 Performance Evaluation
• 6. Applications to the Approaches
  • 6.1 Introduction
  • 6.2 Test Problems
    • 6.2.1 N-Dimensional Rosenbrock Problem
    • 6.2.2 Multistage Test Problem
  • 6.3 Test Results
    • 6.3.1 Scatter Search
    • 6.3.2 Branch and Bound
    • 6.3.3 Grid Environment
• 7. Summary and Future Work

Zielsetzung und Themenschwerpunkte (Objectives and Key Themes)

This diploma thesis investigates distributed approaches for solving discrete, multistage optimization problems. The work explores theoretical backgrounds of optimization, focusing on simulation-based and distributed optimization methods. It investigates and implements solution strategies for derivative-free search methods and addresses the specific challenge of multistage optimization, where the results of each stage depend on previous stages.

• Simulation-based optimization and its challenges.
• Distributed algorithms for solving multistage problems.
• Implementation and evaluation of Scatter Search and Branch and Bound algorithms.
• Application of the algorithms to specific test problems.
• Performance evaluation of the implemented algorithms.

Zusammenfassung der Kapitel (Chapter Summaries)

Chapter 1 introduces the topic. Chapter 2 provides background on optimization, including simulation-based and distributed optimization, and performance evaluation metrics. Chapter 3 discusses discrete multistage processes and their challenges. Chapter 4 reviews existing solution approaches, such as simplex, evolutionary, and mixed-integer methods. Chapter 5 details the implementation of two distributed algorithms: Scatter Search and a stage-based Branch and Bound algorithm. Chapter 6 presents the application of these algorithms to test problems and their corresponding results.

Schlüsselwörter (Keywords)

Multistage optimization, distributed computing, simulation-based optimization, derivative-free optimization, Scatter Search, Branch and Bound, parallel algorithms, scalability, performance evaluation.

• College: University of Siegen
• Grade: 1,3
• Author: Christian Kutsch (Author)
• Publication Year: 2004
• Pages: 83
• Catalog Number: V109467
• ISBN (eBook): 9783640076482
• ISBN (Book): 9783656244813
• Language: English
• Tags: Investigating, Distributed, Approaches, Solving, Discrete, Multistage, Optimization, Problems, Scatter Search