TY - GEN A1 - Steinbach, Marc A1 - Bock, H. Georg A1 - Kostin, Georgii V. A1 - Longman, Richard W. T1 - Mathematical Optimization in Robotics: Towards Automated High Speed Motion Planning N2 - \def\KukaRob {{\sf KUKA IR\,761}} {\small Industrial robots have greatly enhanced the performance of automated manufacturing processes during the last decades. International competition, however, creates an increasing demand to further improve both the accuracy of off-line programming and the resulting cycle times on production lines. To meet these objectives, validated dynamic robot models are required. We describe in detail the development of a generic dynamic model, specialize it to an actual industrial robot \KukaRob, and discuss the problem of dynamic calibration. Efficient and robust trajectory optimization algorithms are then presented which, when integrated into a CAD system, are suitable for routine application in an industrial environment. Our computational results for the \KukaRob\ robot performing a real life transport maneuver show that considerable gains in productivity can be achieved by minimizing the cycle time.} T3 - ZIB-Report - SC-97-03 Y1 - 1997 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-2722 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Algorithms for Multistage Stochastic Programs in Financial Engineering N2 - 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. T3 - ZIB-Report - SC-98-23 KW - multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - finance Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3661 ER - TY - GEN A1 - Steinbach, Marc T1 - Recursive Direct Optimization and Successive Refinement in Multistage Stochastic Programs N2 - 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. T3 - ZIB-Report - SC-98-27 KW - Multistage stochastic programs KW - discrete dynamics KW - tree-sparse QP KW - KKT recursion KW - successive refinement Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3706 ER - TY - GEN A1 - Steinbach, Marc T1 - Autos, Ziegen und Streithähne N2 - Das aus den Medien bekannte umstrittene Ziegenproblem (auch Drei-Türen-Problem genannt) wird vollständig analysiert und gelöst. In der Streitfrage spielen sprachliche Mehrdeutigkeiten der Problemformulierung eine wesentliche Rolle; zudem werden Zufallsereignisse mit willkürlicher Information über deren Ergebnisse verwechselt. Tatsächlich erweisen sich beide strittigen Lösungen als teilweise richtige Bestandteile der Gesamtlösung. Die Argumentation wird in allgemeinverständlicher Sprache geführt und anschliessend durch eine formale mathematische Betrachtung ergänzt. T3 - ZIB-Report - 00-40 KW - Ziegenproblem KW - Zufall KW - Willkür Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6087 ER - TY - GEN A1 - Ehrhardt, Klaus A1 - Steinbach, Marc T1 - Nonlinear Optimization in Gas Networks N2 - The operative planning problem in natural gas distribution networks is addressed. An optimization model focusing on the governing PDE and other nonlinear aspects is presented together with a suitable discretization for transient optimization in large networks by SQP methods. Computational results for a range of related dynamic test problems demonstrate the viability of the approach. T3 - ZIB-Report - 03-46 KW - Gas networks KW - operative planning KW - large-scale optimization Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7687 ER - TY - GEN A1 - Steinbach, Marc T1 - Markowitz Revisited: Single-Period and Multi-Period Mean-Variance Models N2 - 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. T3 - ZIB-Report - SC-99-30 KW - mean-variance analysis KW - downside risk KW - multi-period model Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4183 ER - TY - GEN A1 - Steinbach, Marc T1 - Robust Process Control by Dynamic Stochastic Programming N2 - 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. T3 - ZIB-Report - 04-20 KW - Process control KW - random disturbance KW - multistage stochastic program KW - relatively complete recourse KW - tree-sparse NLP Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7959 ER - TY - GEN A1 - Ehrhardt, Klaus A1 - Steinbach, Marc T1 - KKT Systems in Operative Planning for Gas Distribution Networks N2 - Operative planning in gas networks with prescribed binary decisions yields large scale nonlinear programs defined on graphs. We study the structure of the KKT systems arising in interior methods and present a customized direct solution algorithm. Computational results indicate that the algorithm is suitable for optimization in small and medium-sized gas networks. T3 - ZIB-Report - 04-21 KW - KKT system KW - sparse factorization KW - large-scale nonlinear program KW - gas network KW - operative planning Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7962 ER - TY - GEN A1 - Steinbach, Marc T1 - Hierarchical Sparsity in Multistage Convex Stochastic Programs N2 - 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. T3 - ZIB-Report - 00-15 KW - Multistage Stochastic Programs KW - Hierarchical KKT Sparsity Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5837 ER - TY - GEN A1 - Henrion, Rene A1 - Li, Pu A1 - Möller, Andris A1 - Steinbach, Marc A1 - Wendt, Moritz A1 - Wozny, Günter T1 - Stochastic Optimization for Operating Chemical Processes Under Uncertainty N2 - 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. T3 - ZIB-Report - 01-04 KW - Uncertainty KW - Chemical Processes KW - Multistage Stochastic Programs KW - Probabilistic Constraints Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6304 ER - TY - GEN A1 - Steinbach, Marc T1 - General Information Constraints in Stochastic Programs N2 - 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. T3 - ZIB-Report - 01-24 KW - information constraints KW - general nonanticipativity KW - sigma-fields KW - filtrations KW - scenarios KW - stochastic programs KW - tree-sparse programs Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6502 ER - TY - GEN A1 - Garrido, Izaskun A1 - Steinbach, Marc T1 - A Multistage Stochastic Programming Approach in Real-Time Process Control N2 - 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. T3 - ZIB-Report - 01-05 KW - Process Control KW - Real-Time Optimization KW - Multistage Stochastic Programming Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6317 ER - TY - GEN A1 - Steinbach, Marc T1 - Tree-Sparse Convex Programs N2 - 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. T3 - ZIB-Report - 01-08 KW - Convex program KW - tree KW - discrete-time optimal control multistage stochastic program KW - recursive factorization KW - local projection Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6340 ER - TY - JOUR A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, René A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets JF - Energy Systems N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor were united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We discuss how these changing paradigms lead to new and challenging mathematical optimization problems. This includes the validation of nominations, that asks for the decision if the network’s capacity is sufficient to transport a specific amount of flow, the verification of booked capacities and the detection of available freely allocable capacities, and the topological extension of the network with new pipelines or compressors in order to increase its capacity. In order to solve each of these problems and to provide meaningful results for the practice, a mixture of different mathematical aspects have to be addressed, such as combinatorics, stochasticity, uncertainty, and nonlinearity. Currently, no numerical solver is available that can deal with such blended problems out-of-the-box. The main goal of our research is to develop such a solver, that moreover is able to solve instances of realistic size. In this article, we describe the main ingredients of our prototypical software implementations. Y1 - 2013 U6 - https://doi.org/10.1007/s12667-013-0099-8 VL - 5 IS - 3 SP - 449 EP - 473 PB - Springer Berlin Heidelberg CY - Berlin ER - TY - GEN A1 - Fügenschuh, Armin A1 - Geißler, Björn A1 - Gollmer, Ralf A1 - Hayn, Christine A1 - Henrion, Rene A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Martin, Alexander A1 - Mirkov, Radoslava A1 - Morsi, Antonio A1 - Römisch, Werner A1 - Rövekamp, Jessica A1 - Schewe, Lars A1 - Schmidt, Martin A1 - Schultz, Rüdiger A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Stangl, Claudia A1 - Steinbach, Marc A1 - Willert, Bernhard T1 - Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets N2 - The recently imposed new gas market liberalization rules in Germany lead to a change of business of gas network operators. While previously network operator and gas vendor where united, they were forced to split up into independent companies. The network has to be open to any other gas trader at the same conditions, and free network capacities have to be identified and publicly offered in a non-discriminatory way. We show that these new paradigms lead to new and challenging mathematical optimization problems. In order to solve them and to provide meaningful results for practice, all aspects of the underlying problems, such as combinatorics, stochasticity, uncertainty, and nonlinearity, have to be addressed. With such special-tailored solvers, free network capacities and topological network extensions can, for instance, be determined. T3 - ZIB-Report - 13-13 KW - Gas Market Liberalization KW - Entry-Exit Model KW - Gas Network Access Regulation KW - Mixed-Integer Nonlinear Nonconvex Stochastic Optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-17821 SN - 1438-0064 ER -