Bachelor's Thesis
Refine
Year of publication
Document Type
- Bachelor's Thesis (69) (remove)
Is part of the Bibliography
- no (69)
Keywords
- Benchmark (1)
- Flow Visualization (1)
- HDFS (1)
- Hadoop (1)
- Primal Heuristics, MIP, mixed integer programming, ZI Round, Shift-and-Propagate, optimization (1)
- Uncertainty quantification, Gaussian random fields, ridge, feature detection (1)
- XtreemFS (1)
- distributed storage systems (1)
- dynamic reconfiguration (1)
- replication (1)
Institute
- Mathematical Optimization (28)
- Numerical Mathematics (14)
- Visual Data Analysis (14)
- Visual and Data-centric Computing (14)
- Distributed Algorithms and Supercomputing (8)
- Computational Molecular Design (5)
- Mathematical Optimization Methods (4)
- Therapy Planning (4)
- Visual Data Analysis in Science and Engineering (4)
- Bioinformatics in Medicine (2)
This thesis reports on using dynamic load balancing methods on massively parallel computers in the context of multithreaded computations. In particular we investigate the applicability of a randomized work stealing algorithm to ray tracing and breadth-first search as representatives of real-world applications with dynamic work creation. For our considerations we made use of
current massively parallel hardware accelerators: Nvidia Tesla M2090, and Intel Xeon Phi. For both of the two we demonstrate the suitability of the work stealing scheme for the said real-world applications. Also the necessity of dynamic load balancing for irregular computations on such hardware is illustrated.
Many practically relevant problems can be formulated in terms of a mixed integer programming (MIP) model. MIP denotes the
optimization of a linear objective function under a certain number of linear side constraints including the need for
some of the involved variables to take integral solution values.
Applications of MIP based optimization can be found in the area of public transit,
scheduling, automatic vehicle routing,
network design, etc.
From a complexity point of view, MIP solving is known to be NP-hard and most commonly tried to be solved via
Branch-and-Bound based algorithms. Branch-and-Bound algorithms benefit from early and good feasible solutions of a MIP
in various ways.
Primal heuristics are aimed at finding new solutions during the MIP solving process. There are different types of primal heuristics:
while start heuristics are particularly
valuable to find an early solution, improvement heuristics hopefully drive a given solution further towards optimality.
This thesis focusses on primal heuristics which are part of the MIP-solving framework SCIP.
The first chapter comes with basic definitions and a brief description of SCIP and the test set which we used.
The remainder of the first chapter is an overview of the existing heuristics in SCIP which have been implemented by Achterberg
and Berthold.
In the following chapters we introduce three new heuristics which apply rounding or propagation techniques for their specific purpose,
namely the new rounding heuristic ZI Round, taken from Wallace, a 2-Opt improvement
heuristic for MIP and the propagation heuristic Shift-and-Propagate.
It is characteristic of all three heuristics that they mainly apply computationally inexpensive algorithms.
Each of them is presented in an own chapter, starting with an algorithmic description, followed by implementational details.
All chapters close with a discussion of the computational results obtained with the respective implementations in SCIP.