@misc{Steinbach, author = {Steinbach, Marc}, title = {General Information Constraints in Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6502}, number = {01-24}, abstract = {Scenario tree models of stochastic programs arise naturally under standard nonanticipativity assumptions. We demonstrate how tree-sparse programs cover the general case, with \emph{arbitrary} information constraints. Detailed examples and intuitive interpretations illuminate the basic thoughts behind the abstract but elementary construction.}, language = {en} } @misc{GarridoSteinbach, author = {Garrido, Izaskun and Steinbach, Marc}, title = {A Multistage Stochastic Programming Approach in Real-Time Process Control}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6317}, number = {01-05}, abstract = {Standard model predictive control for real-time operation of industrial production processes may be inefficient in the presence of substantial uncertainties. To avoid overly conservative disturbance corrections while ensuring safe operation, random influences should be taken into account explicitly. We propose a multistage stochastic programming approach within the model predictive control framework and apply it to a distillation process with a feed tank buffering external sources. A preliminary comparison to a probabilistic constraints approach is given and first computational results for the distillation process are presented.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Tree-Sparse Convex Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6340}, number = {01-08}, abstract = {Dynamic stochastic programs are prototypical for optimization problems with an inherent tree structure inducing characteristic sparsity patterns in the KKT systems of interior methods. We propose an integrated modeling and solution approach for such tree-sparse programs. Three closely related natural formulations are theoretically analyzed from a control-theoretic viewpoint and compared to each other. Associated KKT solution algorithms with linear complexity are developed and comparisons to other interior approaches and related problem formulations are discussed.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Robust Process Control by Dynamic Stochastic Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7959}, number = {04-20}, abstract = {Unnecessarily conservative behavior of standard process control techniques can be avoided by stochastic programming models when the distribution of random disturbances is known. In an earlier study we have investigated such an approach for tank level constraints of a distillation process. Here we address techniques that have accelerated the numerical solution of the large and expensive stochastic programs by a factor of six, and then present a refined optimization model for the same application.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Markowitz Revisited: Single-Period and Multi-Period Mean-Variance Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4183}, number = {SC-99-30}, abstract = {Mean-variance portfolio analysis provided the first quantitative treatment of the tradeoff between profit and risk. We investigate in detail the interplay between objective and constraints in a number of single-period variants, including semi-variance models. Particular emphasis is laid on avoiding the penalization of overperformance. The results are then used as building blocks in the development and theoretical analysis of multi-period models based on scenario trees. A key property is the possibility to remove surplus money in future decisions, yielding approximate downside risk minimization.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3661}, number = {SC-98-23}, abstract = {Multistage stochastic programs can be seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within an interior point method. Test runs on a multistage portfolio selection problem demonstrate the performance of the algorithm.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3706}, number = {SC-98-27}, abstract = {The paper presents a new algorithmic approach for multistage stochastic programs which are seen as discrete optimal control problems with a characteristic dynamic structure induced by the scenario tree. To exploit that structure, we propose a highly efficient dynamic programming recursion for the computationally intensive task of KKT systems solution within a primal-dual interior point method. Convergence is drastically enhanced by a successive refinement technique providing both primal and dual initial estimates. Test runs on a multistage portfolio selection problem demonstrate the performance of the method.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Hierarchical Sparsity in Multistage Convex Stochastic Programs}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5837}, number = {00-15}, abstract = {Interior point methods for multistage stochastic programs involve KKT systems with a characteristic global block structure induced by dynamic equations on the scenario tree. We generalize the recursive solution algorithm proposed in an earlier paper so that its linear complexity extends to a refined tree-sparse KKT structure. Then we analyze how the block operations can be specialized to take advantage of problem-specific sparse substructures. Savings of memory and operations for a financial engineering application are discussed in detail.}, language = {en} } @misc{HenrionLiMoelleretal., author = {Henrion, Rene and Li, Pu and M{\"o}ller, Andris and Steinbach, Marc and Wendt, Moritz and Wozny, G{\"u}nter}, title = {Stochastic Optimization for Operating Chemical Processes Under Uncertainty}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6304}, number = {01-04}, abstract = {Mathematical optimization techniques are on their way to becoming a standard tool in chemical process engineering. While such approaches are usually based on deterministic models, uncertainties such as external disturbances play a significant role in many real-life applications. The present article gives an introduction to practical issues of process operation and to basic mathematical concepts required for the explicit treatment of uncertainties by stochastic optimization.}, language = {en} } @misc{BorndoerferDovicaNowaketal., author = {Bornd{\"o}rfer, Ralf and Dovica, Ivan and Nowak, Ivo and Schickinger, Thomas}, title = {Robust Tail Assignment}, organization = {Zuse-Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11707}, number = {10-08}, abstract = {We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.}, language = {en} } @misc{Schweiger, type = {Master Thesis}, author = {Schweiger, Jonas}, title = {Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12206}, school = {Zuse Institute Berlin (ZIB)}, pages = {149}, abstract = {Telecommunication is fundamental for the information society. In both, the private and the professional sector, mobile communication is nowadays taken for granted. Starting primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. In the year 2009, 19 million users generated over 33 million GB of traffic using mobile data services. The 3rd generation networks (3G or UMTS) in Germany comprises over 39,000 base stations with some 120,000 cells. From 1998 to 2008, the four network operators in Germany invested over 33 billion Euros in their infrastructure. A careful allocation of the resources is thus crucial for the profitability for a network operator: a network should be dimensioned to match customers demand. As this demand evolves over time, the infrastructure has to evolve accordingly. The demand evolution is hard to predict and thus constitutes a strong source of uncertainty. Strategic network planning has to take this uncertainty into account, and the planned network evolution should adapt to changing market conditions. The application of superior planning methods under the consideration of uncertainty can improve the profitability of the network and creates a competitive advantage. Multistage stochastic programming is a suitable framework to model strategic telecommunication network planning. We present mathematical models and effective optimization procedures for strategic cellular network design. The demand evolution is modeled as a continuous stochastic process which is approximated by a discrete scenario tree. A tree-stage approach is used for the construction of non-uniform scenario trees that serve as input of the stochastic program. The model is calibrated by historical traffic observations. A realistic system model of UMTS radio cells is used that determines coverage areas and cell capacities and takes signal propagation and interferences into account. The network design problem is formulated as a multistage stochastic mixed integer linear program, which is solved using state-of-the-art commercial MIP solvers. Problem specific presolving is proposed to reduce the problem size. Computational results on realistic data is presented. Optimization for the expected profit and the conditional value at risk are performed and compared.}, language = {en} } @misc{EisenblaetterSchweiger, author = {Eisenbl{\"a}tter, Andreas and Schweiger, Jonas}, title = {Multistage Stochastic Programming in Strategic Telecommunication Network Planning}, doi = {10.1007/s10287-012-0143-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12232}, number = {11-06}, abstract = {Mobile communication is nowadays taken for granted. Having started primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. Operators are facing the challenge to match the demand by continuously expanding and upgrading the network infrastructure. However, the evolution of the customer's demand is uncertain. We introduce a novel (long-term) network planning approach based on multistage stochastic programming, where demand evolution is considered as a stochastic process and the network is extended as to maximize the expected profit. The approach proves capable of designing large-scale realistic UMTS networks with a time-horizon of several years. Our mathematical optimization model, the solution approach, and computational results are presented in this paper.}, language = {en} } @misc{Schweiger, author = {Schweiger, Jonas}, title = {Gas network extension planning for multiple demand scenarios}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51030}, abstract = {Today's gas markets demand more flexibility from the network operators which in turn have to invest into their network infrastructure. As these investments are very cost-intensive and long-living, network extensions should not only focus on one bottleneck scenario, but should increase the flexibility to fulfill different demand scenarios. We formulate a model for the network extension problem for multiple demand scenarios and propose a scenario decomposition. We solve MINLP single-scenario sub-problems and obtain valid bounds even without solving them to optimality. Heuristics prove capable of improving the initial solutions substantially. Results of computational experiments are presented.}, language = {en} }