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. [...]
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
Objectives and Topics
This thesis focuses on the implementation and analysis of distributed optimization strategies for discrete, multistage problems. The research aims to evaluate cost-effective computing alternatives, specifically by utilizing distributed algorithms like Scatter Search and Branch and Bound, to solve complex, simulation-based optimization tasks efficiently while addressing the challenges of nonlinearity and high computational demand.
- Simulation-based optimization in distributed environments
- Algorithmic implementation of Scatter Search and Branch and Bound
- Performance metrics: speedup, efficiency, and scalability
- Constraint handling in multistage optimization processes
- Comparative analysis of distributed algorithms for complex test functions
Excerpt from the Book
5.4.1 Introduction
Branch and Bound is implemented to solve multistage problems one stage at a time, rather than with brute force. It uses mixed integer strategies combined with a nonlinear search method. The purpose of the strategy is to find a "good" solution as quickly as possible, rather than finding an optimal one after many iterations. This is especially important for real world problems, where cost estimations have to be made and evaluations are performed based on simulations (i.e. see Chapter 3).
Branch and Bound is a heuristic that works on the idea of successive partitioning of the search space [MF00]. It needs a lower bound on the cost for any particular solution (or an upper bound, depending on the problem). Therefore, the procedure is: For a solution xa the objective function value can be determined and compared with the lower bound. If it is above that threshold, the branch can be pruned away and the optimization can concentrate on intensifying the other branches.
It is apparent that this process can only be applied to discrete values, as branches have to be distinguishable from each other and enumerable. Therefore, most applications for the Branch and Bound approach published in the last 2 decades are of this kind. However in recent years, strategies have been developed to solve nonlinear problems (NLP) with Branch and Bound and with the other mixed integer approaches that were previously mentioned.
This section discusses the application of a Branch and Bound approach to a nonlinear multistage optimization problem of the class introduced in Chapter 3, while using techniques from the MVP and MINLP strategies introduced in Section 4.4. This approach was proposed by Markus Gerdes in [Ger04b] and has been implemented in close consultation with him.
The implementation is focused on parallel execution and incorporates a high degree of scalability. Test results, in combination with a multistage test problem, can be found in Chapter 6.
Summary of Chapters
1. Introduction: Presents the motivation for distributed nonlinear optimization and outlines the two primary algorithms implemented in this thesis.
2. Optimization: Covers the theoretical background of simulation-based optimization, distributed computing, and performance metrics.
3. Discrete Multistage Processes: Discusses the nature of multistage problems, specifically within manufacturing contexts and the associated computational challenges.
4. Solution Approaches: Introduces several non-derivative optimization strategies, including Simplex, Evolutionary, and Mixed Integer methods.
5. Implementation of Two Algorithms for Solving Multistage Problems: Details the specific Java-based implementation of Scatter Search and Branch and Bound for distributed environments.
6. Applications to the Approaches: Applies the developed algorithms to test problems, including the Rosenbrock function, and analyzes performance results.
7. Summary and Future Work: Reviews the research outcomes and suggests potential improvements for future extensions of the algorithms.
Keywords
Distributed Optimization, Multistage Problems, Scatter Search, Branch and Bound, Simulation-Based Optimization, Parallel Computing, Grid Computing, Performance Evaluation, Speedup, Efficiency, Scalability, Constraint Handling, Nonlinear Optimization, Algorithm Implementation, Optimization Heuristics
Frequently Asked Questions
What is the primary focus of this research?
The thesis focuses on investigating and implementing distributed optimization strategies for solving discrete, multistage optimization problems.
Which algorithms are central to the study?
The two primary meta-heuristic and discrete optimization algorithms implemented and analyzed are Scatter Search and Branch and Bound.
What is the core research objective?
The objective is to enable the efficient, distributed calculation of multistage simulation-based problems, which are otherwise computationally expensive.
What scientific methods are applied?
The study employs algorithm implementation in JAVA, performance evaluation through metrics like speedup and efficiency, and tests against established functions like the Rosenbrock problem.
What topics does the main body cover?
The main sections cover optimization theory, the architecture of multistage processes, detailed algorithm design, parallelization techniques, and experimental results from test applications.
What are the characterizing keywords of the work?
Key terms include distributed optimization, multistage problems, Scatter Search, Branch and Bound, scalability, and simulation-based optimization.
How does the Branch and Bound algorithm handle constraints?
It integrates techniques from MVP and MINLP, performing discretizations and using an NLP solver, while pruning branches that exceed cost thresholds.
What distinguishes the implemented Scatter Search from standard versions?
The implementation is specifically designed for parallel execution and incorporates Path Relinking to handle infeasible solutions efficiently in a distributed environment.
How is the performance of the distributed algorithms measured?
Performance is assessed using absolute and relative speedup, efficiency ratios relative to the number of processors, and scalability benchmarks.
- Quote paper
- Christian Kutsch (Author), 2004, Investigating Distributed Approaches for Solving Discrete, Multistage Optimization Problems, Munich, GRIN Verlag, https://www.grin.com/document/109467
