Refine
Year of publication
- 2012 (6) (remove)
Document Type
- ZIB-Report (5)
- Article (1)
Is part of the Bibliography
- no (6)
Keywords
- Buchungsvalidierung (1)
- Gasnetzplanung (1)
- Nominierungsvalidierung (1)
- Technische Kapazitäten (1)
- Topologieplanung (1)
- competitive analysis (1)
- elevator control, online optimization, reoptimization algorithms, column generation (1)
- online algorithms (1)
- online algorithms, stochastic dominance, algorithm analysis, Markov chains (1)
- probabilistic analysis (1)
Institute
The task of an elevator control is to schedule the elevators of a group such
that small waiting and travel times for the passengers are obtained. We present an exact
reoptimization algorithm for this problem. A reoptimization algorithm computes a
new schedule for the elevator group each time a new passenger arrives. Our algorithm
uses column generation techniques and is, to the best of our knowledge, the first exact
reoptimization algorithms for a group of passenger elevators. To solve the column
generation problem, we propose a Branch & Bound method.
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.
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints.
We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.
Die mittel- und längerfristige Planung für den Gastransport hat sich durch
Änderungen in den regulatorischen Rahmenbedingungen stark verkompliziert.
Kernpunkt ist die Trennung von Gashandel und -transport. Dieser Artikel
diskutiert die hieraus resultierenden mathematischen Planungsprobleme,
welche als Validierung von Nominierungen und Buchungen, Bestimmung der
technischen Kapazität und Topologieplanung bezeichnet werden. Diese
mathematischen Optimierungsprobleme werden vorgestellt und Lösungsansätze
skizziert.
In the last 20 years competitive analysis has become the main tool for
analyzing the quality of online algorithms. Despite of this,
competitive analysis has also been criticized: It sometimes cannot
discriminate between algorithms that exhibit significantly different
empirical behavior, or it even favors an algorithm that is worse from
an empirical point of view. Therefore, there have been several
approaches to circumvent these drawbacks. In this survey, we discuss
probabilistic alternatives for competitive analysis.