TY - GEN
A1 - Wolf, Thomas
T1 - A Study of Genetic Algorithms solving a combinatorial Puzzle
N2 - The suitability of Genetic Algorithms (GAs) to solve a combinatorial problem with only one solution is investigated. The dependence of the performance is studied for GA-hard and GA-soft fitness functions, both with a range of different parameter values and different encodings.
T3 - ZIB-Report - SC-98-01
Y1 - 1998
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3445
ER -
TY - GEN
A1 - Orlowski, Sebastian
A1 - Werner, Axel
A1 - Wessäly, Roland
T1 - Estimating trenching costs in FTTx network planning
N2 - In this paper we assess to which extent trenching costs of an FTTx network are unavoidable, even if technical side constraints are neglected. For that purpose we present an extended Steiner tree model. Using a variety of realistic problem instances we demonstrate that the total trenching cost can only be reduced by about 5 percent in realistic scenarios. This work has been funded by BMBF (German Federal Ministry of Education and Research) within the program "KMU-innovativ".
T3 - ZIB-Report - 11-49
KW - Optical access networks
KW - Optimization
KW - Steiner trees
Y1 - 2012
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14884
SN - 1438-0064
ER -
TY - GEN
A1 - Wiebel, Alexander
A1 - Vos, Frans M.
A1 - Hege, Hans-Christian
T1 - Perception-Oriented Picking of Structures in Direct Volumetric Renderings
N2 - Radiologists from all application areas are trained to read slice-based visualizations of 3D medical image data. Despite the numerous
examples of sophisticated three-dimensional renderings, especially all variants of direct volume rendering, such methods are
often considered not very useful by radiologists who prefer slice-based visualization. Just recently there have been attempts to bridge this
gap between 2D and 3D renderings. These attempts include specialized techniques for volume picking that result in repositioning slices.
In this paper, we present a new volume picking technique that, in contrast to previous work, does not require pre-segmented data or metadata. The positions picked by our method are solely based on the data itself, the transfer function and,
most importantly, on the way the volumetric rendering is perceived by viewers. To demonstrate the usefulness of the proposed method
we apply it for automatically
repositioning slices in an abdominal MRI
scan, a data set from a flow simulation and a number of other volumetric scalar fields. Furthermore we discuss how the method can be implemented in combination with various different volumetric rendering techniques.
T3 - ZIB-Report - 11-45
KW - DVR
KW - picking
KW - pointing
KW - direct volume rendering
Y1 - 2011
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14343
SN - 1438-0064
ER -
TY - GEN
A1 - Nielsen, Adam
A1 - Weber, Marcus
T1 - Computing the nearest reversible Markov chain
N2 - Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.
T3 - ZIB-Report - 14-48
KW - Reversible Markov Chain
KW - Convex Optimization
KW - MSM
Y1 - 2014
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53292
SN - 1438-0064
ER -
TY - JOUR
A1 - Nielsen, Adam
A1 - Weber, Marcus
T1 - Computing the nearest reversible Markov chain
JF - Numerical Linear Algebra with Applications
N2 - Reversible Markov chains are the basis of many applications. However, computing transition probabilities by a finite sampling of a Markov chain can lead to truncation errors. Even if the original Markov chain is reversible, the approximated Markov chain might be non-reversible and will lose important properties, like the real valued spectrum. In this paper, we show how to find the closest reversible Markov chain to a given transition matrix. It turns out that this matrix can be computed by solving a convex minimization problem.
KW - Reversible Markov Chain
KW - Convex Optimization
KW - MSM
Y1 - 2015
U6 - http://dx.doi.org/10.1002/nla.1967
VL - 22
IS - 3
SP - 483
EP - 499
ER -
TY - THES
A1 - Witzig, Jakob
T1 - Effiziente Reoptimierung in Branch&Bound-Verfahren für die Steuerung von Aufzügen
N2 - Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen
ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei
diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten
und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage
und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug
mit gleicher Fahrtrichtung und ausreichend Kapazität. Die entsprechende Zieletage
wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen
konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit
eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf
der Startetage seine gewünschte Zieletage angibt und eine Rückmeldung vom System
erhält, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel,
die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei
der Berechnung warte- und reisezeitminimaler Fahrpläne ist das momentane Verkehrsmuster.
Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden
vornehmen. So ist es typisch für die Morgenstunden, dass jeder Passagier auf einer
Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben.
Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen.
Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere
durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme.
In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme
des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt.
Eine solche Momentaufnahme werden wir im späteren Verkauf als Schnappschussproblem
bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems
eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug
er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen
Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor
Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System
allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit.
Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will,
kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem
UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch
kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist
hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung
die weitere Verkehrsentwicklung mit einbezogen werden kann.
VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die
Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser
Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines
Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten
Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion
zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung
innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer
Menge zulässiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung
zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen
aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den
wichtigen Informationen gehört der konstruierte Suchbaum der vorherigen Iterationsrunde
mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren
bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des
Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und
Aufbereitung von Informationen nennen wir Warmstart.
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42210
ER -
TY - GEN
A1 - Quer, Jannes
A1 - Donati, Luca
A1 - Keller, Bettina
A1 - Weber, Marcus
T1 - An automatic adaptive importance sampling algorithm for molecular dynamics in reaction coordinates
N2 - In this article we propose an adaptive importance sampling scheme for dynamical quantities of high dimensional complex systems which are metastable. The main idea of this article is to combine a method coming from Molecular Dynamics Simulation, Metadynamics, with a theorem from stochastic analysis, Girsanov's theorem. The proposed algorithm has two advantages compared to a standard estimator of dynamic quantities: firstly, it is possible to produce estimators with a lower variance and, secondly, we can speed up the sampling. One of the main problems for building importance sampling schemes for metastable systems is to find the metastable region in order to manipulate the potential accordingly. Our method circumvents this problem by using an assimilated version of the Metadynamics algorithm and thus creates a non-equilibrium dynamics which is used to sample the equilibrium quantities.
T3 - ZIB-Report - 17-09
KW - Adaptive Importance Sampling
KW - Molecular Dynamics
KW - Metastability
KW - Variance Reduction
KW - Non Equilibrium Sampling
KW - Metadynamics
KW - Girsanov
Y1 - 2017
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-62075
SN - 1438-0064
ER -
TY - GEN
A1 - Baum, Daniel
A1 - Lindow, Norbert
A1 - Hege, Hans-Christian
A1 - Lepper, Verena
A1 - Siopi, Tzulia
A1 - Kutz, Frank
A1 - Mahlow, Kristin
A1 - Mahnke, Heinz-Eberhard
T1 - Revealing hidden text in rolled and folded papyri
N2 - Ancient Egyptian papyri are often folded, rolled up or kept as small packages, sometimes even sealed. Physically unrolling or unfolding these packages might severely damage them. We demonstrate a way to get access to the hidden script without physical unfolding by employing computed tomography and mathematical algorithms for virtual unrolling and unfolding. Our algorithmic approaches are combined with manual interaction. This provides the necessary flexibility to enable the unfolding of even complicated and partly damaged papyrus packages. In addition, it allows us to cope with challenges posed by the structure of ancient papyrus, which is rather irregular, compared to other writing substrates like metallic foils or parchment. Unfolding of packages is done in two stages. In the first stage, we virtually invert the physical folding process step by step until the partially unfolded package is topologically equivalent to a scroll or a papyrus sheet folded only along one fold line. To minimize distortions at this stage, we apply the method of moving least squares. In the second stage, the papyrus is simply flattened, which requires the definition of a medial surface. We have applied our software framework to several papyri. In this work, we present the results of applying our approaches to mockup papyri that were either rolled or folded along perpendicular fold lines. In the case of the folded papyrus, our approach represents the first attempt to address the unfolding of such complicated folds.
T3 - ZIB-Report - 17-02
KW - unfolding, papyri, computed tomography
Y1 - 2017
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-61826
SN - 1438-0064
ER -
TY - GEN
A1 - Schäfer, Patrick
T1 - Bag-Of-SFA-Symbols in Vector Space (BOSS VS)
N2 - Time series classification mimics the human understanding of similarity. When it comes to larger datasets, state of the art classifiers reach their limits in terms of unreasonable training or testing times. One representative example is the 1-nearest-neighbor DTW classifier (1-NN DTW) that is commonly used as the benchmark to compare to and has several shortcomings: it has a quadratic time and it degenerates in the presence of noise. To reduce the computational complexity lower bounding techniques or recently a nearest centroid classifier have been introduced. Still, execution times to classify moderately sized datasets on a single core are in the order of hours. We present our Bag-Of-SFA-Symbols in Vector Space (BOSS VS) classifier that is robust and accurate due to invariance to noise, phase shifts, offsets, amplitudes and occlusions. We show that it is as accurate while being multiple orders of magnitude faster than state of the art classifiers. Using the BOSS VS allows for mining massive time series datasets and real-time analytics.
T3 - ZIB-Report - 15-30
KW - Time Series
KW - Classification
KW - Data Mining
Y1 - 2015
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54984
SN - 1438-0064
ER -
TY - GEN
A1 - Pfeuffer, Frank
A1 - Werner, Axel
T1 - Adaptive telecommunication network operation with a limited number of reconfigurations
N2 - Rising traffic in telecommunication networks lead to rising energy costs for the network operators. Meanwhile, increased flexibility of the networking hardware may help to realize load-adaptive operation of the networks to cut operation costs. To meet network operators’ concerns over stability, we propose to switch network configurations only a limited number of times per day. We present a method for the integrated computation of optimal switching times and network configurations that alternatingly solves mixed-integer programs and constrained shortest cycle problems in a certain graph. Similarly to the Branch & Bound Algorithm, it uses lower and upper bounds on the optimum value and allows for pivoting strategies to guide the computation and avoid the solution of irrelevant subproblems. The algorithm can act as a framework to be adapted and applied to suitable problems of different origin.
T3 - ZIB-Report - 15-36
KW - Telecommunication
KW - Network Design
KW - Dynamic Traffic
KW - Branch and Bound
Y1 - 2015
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55547
SN - 1438-0064
ER -
TY - GEN
A1 - Clasen, Malte
A1 - Paar, Philip
A1 - Prohaska, Steffen
T1 - Level of Detail for Trees Using Clustered Ellipsoids
N2 - We present a level of detail method for trees based on ellipsoids and lines. We leverage the Expectation Maximization algorithm with a Gaussian Mixture Model to create a hierarchy of high-quality leaf clusterings, while the branches are simplified using agglomerative bottom-up clustering to preserve the connectivity. The simplification runs in a preprocessing step and requires no human interaction. For a fly by over and through a scene of 10k trees, our method renders on average at 40 ms/frame, up to 6 times faster than billboard clouds with comparable artifacts.
T3 - ZIB-Report - 11-41
KW - level of detail
KW - rendering
KW - natural scene
KW - Gaussian mixture model
Y1 - 2011
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14251
SN - 1438-0064
ER -
TY - GEN
A1 - Weber, Britta
A1 - Tranfield, Erin M.
A1 - Höög, Johanna L.
A1 - Baum, Daniel
A1 - Antony, Claude
A1 - Hyman, Tony
A1 - Verbavatz, Jean-Marc
A1 - Prohaska, Steffen
T1 - Automated stitching of microtubule centerlines across serial electron tomograms
N2 - Tracing microtubule centerlines in serial section electron tomography requires microtubules to be stitched across sections, that is lines from different sections need to be aligned, endpoints need to be matched at section boundaries to establish a correspondence between neighboring sections, and corresponding lines need to be connected across multiple sections. We present computational methods for these tasks: 1) An initial alignment is computed using a distance compatibility graph. 2) A fine alignment is then computed with a probabilistic variant of the iterative closest points algorithm, which we extended to handle the orientation of lines by introducing a periodic random variable to the probabilistic formulation. 3) Endpoint correspondence is established by formulating a matching problem in terms of a Markov random field and computing the best matching with belief propagation. Belief propagation is not generally guaranteed to converge to a minimum. We show how convergence can be achieved, nonetheless, with minimal manual input. In addition to stitching microtubule centerlines, the correspondence is also applied to transform and merge the electron tomograms. We applied the proposed methods to samples from the mitotic spindle in C. elegans, the meiotic spindle in X. laevis, and sub-pellicular microtubule arrays in T. brucei. The methods were able to stitch microtubules across section boundaries in good agreement with experts’ opinions for the spindle samples. Results, however, were not satisfactory for the microtubule arrays. For certain experiments, such as an analysis of the spindle, the proposed methods can replace manual expert tracing and thus enable the analysis of microtubules over long distances with reasonable manual effort.
T3 - ZIB-Report - 14-41
KW - electron tomography
KW - microtubules
KW - serial sectioning
KW - image analysis
KW - geometry reconstruction
KW - image and geometry alignment
KW - point correspondence
Y1 - 2014
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-52958
SN - 1438-0064
ER -
TY - GEN
A1 - Hiller, Benjamin
A1 - Vredeveld, Tjark
T1 - Stochastic dominance analysis of Online Bin Coloring algorithms
N2 - This paper proposes a new method for probabilistic analysis of online algorithms. It is based on the notion of stochastic dominance. We develop the method for
the online bin coloring problem introduced by Krumke et al (2008). Using methods for the stochastic
comparison of Markov chains we establish the result that the performance of the online algorithm GreedyFit is stochastically better than the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic
picture than competitive analysis and explains the behavior observed in simulations.
T3 - ZIB-Report - 12-42
KW - online algorithms, stochastic dominance, algorithm analysis, Markov chains
Y1 - 2012
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16502
SN - 1438-0064
ER -
TY - GEN
A1 - Zakrzewska, Anna
A1 - D'Andreagiovanni, Fabio
A1 - Ruepp, Sarah
A1 - Berger, Michael S.
T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks
N2 - We propose a novel optimization model for resource assignment in heterogeneous wireless network. The model adopts two objective functions maximizing the number of served users and the minimum granted utility at once. A distinctive feature of our new model is to consider two consecutive time slots, in order to include handover as an additional decision dimension.
Furthermore, the solution algorithm that we propose refines a heuristic solution approach recently proposed in literature, by considering a real joint optimization of the considered resources. The simulation study shows that the new model leads to a significant reduction in handover frequency, when compared to a traditional scheme based on maximum SNR.
T3 - ZIB-Report - 13-63
KW - Heterogeneous Wireless Networks, Biobjective Optimization, Mixed Integer Linear Programming, Simulation
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42675
UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6576416&isnumber=6576384
SN - 1438-0064
ER -
TY - GEN
A1 - Bley, Andreas
A1 - D'Andreagiovanni, Fabio
A1 - Karch, Daniel
T1 - Scheduling technology migration in WDM Networks
N2 - The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).
T3 - ZIB-Report - 13-62
KW - Scheduling, Extended Formulations, Network Migration, WDM Networks
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42654
UR - http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6507677&isnumber=6507670
SN - 1438-0064
ER -
TY - GEN
A1 - Büsing, Christina
A1 - D'Andreagiovanni, Fabio
T1 - A new theoretical framework for Robust Optimization under multi-band uncertainty
N2 - We provide an overview of our main results about studying Linear Programming Problems whose coefficient matrix is subject to uncertainty and the uncertainty is modeled through a multi-band set. Such an uncertainty set generalizes the classical one proposed by Bertsimas and Sim and is particularly suitable in the common case of arbitrary non-symmetric distributions of the parameters. Our investigations were inspired by practical needs of our industrial partner in ongoing projects with focus on the design of robust telecommunications networks.
T3 - ZIB-Report - 13-61
KW - Robust Optimization, Uncertainty Set, Multiband Robustness, Network Design
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42644
UR - http://www.springer.com/business+%26+management/operations+research/book/978-3-319-00794-6
SN - 1438-0064
ER -
TY - GEN
A1 - Bauschert, Thomas
A1 - Büsing, Christina
A1 - D'Andreagiovanni, Fabio
A1 - Koster, Arie M. C. A.
A1 - Kutschka, Manuel
A1 - Steglich, Uwe
T1 - Network Planning under Demand Uncertainty with Robust Optimization
N2 - The planning of a communication network is inevitably depending on the quality of both the planning tool and the demand forecast used. In this article, we show exemplarily how the emerging area of Robust Optimization can advance the network planning by a more accurate mathematical description of the demand uncertainty. After a general introduction of the concept and its application to a basic network design problem, we present two applications: multi-layer and mixed-line-rate network design. We conclude with a discussion of extensions of the robustness concept to increase the accuracy of handling uncertainties.
T3 - ZIB-Report - 13-59
KW - Network Design, Demand Uncertainty, Robust Optimization, Telecommunications
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42557
SN - 1438-0064
ER -
TY - THES
A1 - Witzig, Jakob
T1 - Reoptimization Techniques in MIP Solvers
N2 - Many optimization problems can be modeled as Mixed Integer Programs (MIPs). In general, MIPs cannot be solved efficiently, since solving MIPs is NP-hard, see, e.g., Schrijver, 2003. Common methods for solving NP-hard problems are branch-and-bound and column generation. In the case of column generation, the original problem
becomes decomposed or re-formulated into one ore more smaller subproblems, which are easier to solve. Each of these subproblems is solved separately and recurrently, which can be interpreted as solving a sequence of optimization problems.
In this thesis, we consider a sequence of MIPs which only differ in the respective objective functions. Furthermore, we assume each of these MIPs get solved with a branch-and-bound algorithm. This thesis aims to figure out whether the solving process of a given sequence of MIPs can be accelerated by reoptimization. As reoptimization we understand starting the solving process
of a MIP of this sequence at a given frontier of a search tree corresponding to another MIP of this sequence.
At the beginning we introduce an LP-based branch-and-bound algorithm. This algorithm is inspired by the reoptimizing algorithm of Hiller, Klug, and the author of this
thesis, 2013. Since most of the state-of-the-art MIP
solvers come to decisions based on dual information, which leads to the loss of feasible solutions after changing the objective function, we present a technique to guarantee optimality despite using these information. A decision is based on a dual information if this decision is valid for at least one feasible solution, whereas a decision is based on a primal information if this decision is valid for all feasible solutions. Afterwards, we consider representing the search frontier of the tree by a set of nodes of a given size. We call this the Tree Compression Problem. Moreover, we present a criterion characterizing the similarity of two objective functions. To evaluate our approach of reoptimization we extend the well-known and well-maintained MIP solver SCIP to an LP-based branch-and-bound framework, introduce two heuristics for solving the Tree Compression Problem, and a primal heuristic which is especially fitted to column generation. Finally, we present computational experiments on several problem classes, e.g., the Vertex Coloring and k-Constrained Shortest Path. Our experiments show, that a straightforward reoptimization, i.e., without additional heuristics, provides no benefit in general. However, in combination with the techniques and methods presented in this thesis, we can accelerate the solving of a given sequence up to the factor 14. For this purpose it is essential to take the differences of the objective functions into account and to restart the reoptimization, i.e., solve the subproblem from scratch, if the objective functions are not similar enough. Finally, we discuss the possibility to parallelize the solving process of the search frontier at the beginning of each solving process.
Y1 - 2014
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-54067
ER -
TY - GEN
A1 - D'Andreagiovanni, Fabio
A1 - Raymond, Annie
T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling
N2 - A central assumption in classical optimization is that all the input data of a
problem are exact. However, in many real-world problems, the input data are subject
to uncertainty. In such situations, neglecting uncertainty may lead to nominally optimal
solutions that are actually suboptimal or even infeasible. Robust optimization
offers a remedy for optimization under uncertainty by considering only the subset of
solutions protected against the data deviations. In this paper, we provide an overview
of the main theoretical results of multiband robustness, a new robust optimization
model that extends and refines the classical theory introduced by Bertsimas and Sim.
After introducing some new results for the special case of pure binary programs, we
focus on the harvest scheduling problem and show how multiband robustness can
be adopted to tackle the uncertainty affecting the volume of produced timber and
grant a reduction in the price of robustness.
T3 - ZIB-Report - 13-76
KW - Data Uncertainty
KW - Robust Optimization
KW - Multiband Robustness
KW - Harvest Scheduling
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-43380
SN - 1438-0064
ER -
TY - GEN
A1 - D'Andreagiovanni, Fabio
A1 - Krolikowski, Jonatan
A1 - Pulaj, Jonad
T1 - A hybrid primal heuristic for Robust Multiperiod Network Design
N2 - We investigate the Robust Multiperiod Network Design Problem, a generalization of the classical Capacitated Network Design Problem that additionally considers multiple design periods and provides solutions protected against traffic uncertainty.
Given the intrinsic difficulty of the problem, which proves challenging even for state-of-the art commercial solvers, we propose a hybrid primal heuristic based on the combination of ant colony optimization and an exact large neighborhood search. Computational experiments on a set of realistic instances from the SNDlib show that our heuristic can find solutions of extremely good quality with low optimality gap.
T3 - ZIB-Report - 13-78
KW - Multiperiod Network Design, Traffic Uncertainty, Robust Optimization, Multiband Robustness, Hybrid Heuristics
Y1 - 2013
U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-44081
SN - 1438-0064
ER -