@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 = {On PDE Solution in Transient Optimization of Gas Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8215}, number = {04-46}, abstract = {Operative planning in gas distribution networks leads to large-scale mixed-integer optimization problems involving a hyperbolic PDE defined on a graph. We consider the NLP obtained under prescribed combinatorial decisions---or as relaxation in a branch and bound framework, addressing in particular the KKT systems arising in primal-dual interior methods. We propose a custom solution algorithm using sparse local projections, based on the KKT systems' structual properties induced by the discretized gas flow equations in combination with the underlying network topology. The numerical efficiency and accuracy of the algorithm are investigated, and detailed computational comparisons with a control space method and with the multifrontal solver MA27 are provided.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Optimization Models for Operative Planning in Drinking Water Networks}, doi = {10.1007/s11081-008-9040-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8237}, number = {04-48}, abstract = {The topic of this paper is minimum cost operative planning of pressurized water supply networks over a finite horizon and under reliable demand forecast. Since this is a very hard problem, it is desirable to employ sophisticated mathematical algorithms, which in turn calls for carefully designed models with suitable properties. The paper develops a nonlinear mixed integer model and a nonlinear programming model with favorable properties for gradient-based optimization methods, based on smooth component models for the network elements. In combination with further nonlinear programming techniques (to be reported elsewhere), practically satisfactory near-optimum solutions even for large networks can be generated in acceptable time using standard optimization software on a PC workstation. Such an optimization system is in operation at Berliner Wasserbetriebe.}, 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{EhrhardtSteinbach, author = {Ehrhardt, Klaus and Steinbach, Marc}, title = {KKT Systems in Operative Planning for Gas Distribution Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7962}, number = {04-21}, abstract = {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.}, language = {en} } @misc{EhrhardtSteinbach, author = {Ehrhardt, Klaus and Steinbach, Marc}, title = {Nonlinear Optimization in Gas Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7687}, number = {03-46}, abstract = {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.}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Topological Index Criteria in DAE for Water Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8821}, number = {05-49}, abstract = {The dynamics of pressurized water distribution networks are naturally modeled by differential algebraic equations (DAE). This paper investigates fundamental structural properties of such a DAE model under weak regularity assumptions. The usual partial derivative-based index-1 condition is shown to be necessary and sufficient for several index concepts, as well as sufficient for solvability in a strong sense. Using the physical properties of nonlinear network elements and the inherent saddle point structure of network hydraulics, we then derive purely topological index criteria based on the network graph and the choice of control variables. Several examples illustrate the theoretical results and explore different non-index-1 situations. A brief discussion of the implications for operative planning by discrete time DAE boundary value problems concludes the paper.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Nonlinear Programming Techniques for Operative Planning in Large Drinking Water Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8657}, number = {05-31}, abstract = {Mathematical decision support for operative planning in water supply systems is highly desirable but leads to very difficult optimization problems. We propose a nonlinear programming approach that yields practically satisfactory operating schedules in acceptable computing time even for large networks. Based on a carefully designed model supporting gradient-based optimization algorithms, this approach employs a special initialization strategy for convergence acceleration, special minimum up and down time constraints together with pump aggregation to handle switching decisions, and several network reduction techniques for further speed-up. Results for selected application scenarios at Berliner Wasserbetriebe demonstrate the success of the approach.}, language = {en} } @misc{BurgschweigerGnaedigSteinbach, author = {Burgschweiger, Jens and Gn{\"a}dig, Bernd and Steinbach, Marc}, title = {Optimierte Tagesplanung im Berliner Trinkwassernetz}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8668}, number = {05-32}, abstract = {Der Artikel beschreibt ein mathematisches Optimierungssystem zur Betriebsplanung in großen Wassernetzen, das bei den Berliner Wasserbetrieben eingesetzt wird. F{\"u}r das Berliner Versorgungsnetz werden Optimierungsergebnisse vorgestellt.}, language = {de} } @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 = {Optimal Motion Design Using Inverse Dynamics.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2818}, number = {SC-97-12}, abstract = {Increasing demands on industrial robot operation call for optimal motion planning based on dynamic models. The resulting mathematical problems can be handled efficiently by sparse direct boundary value problem methods. Within this framework we propose a new solution technique that is closely related to the conventional kinematic approach: it eliminates the need for numerical integration of differential equations. First optimization results on a real life transport maneuver demonstrate that the technique may save over 50\,\\%\ computation time.}, 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{SteinbachBockKostinetal., author = {Steinbach, Marc and Bock, H. Georg and Kostin, Georgii V. and Longman, Richard W.}, title = {Mathematical Optimization in Robotics: Towards Automated High Speed Motion Planning}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2722}, number = {SC-97-03}, abstract = {\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.}}, language = {en} } @misc{Steinbach, author = {Steinbach, Marc}, title = {Autos, Ziegen und Streith{\"a}hne}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6087}, number = {00-40}, abstract = {Das aus den Medien bekannte umstrittene Ziegenproblem (auch Drei-T{\"u}ren-Problem genannt) wird vollst{\"a}ndig analysiert und gel{\"o}st. In der Streitfrage spielen sprachliche Mehrdeutigkeiten der Problemformulierung eine wesentliche Rolle; zudem werden Zufallsereignisse mit willk{\"u}rlicher Information {\"u}ber deren Ergebnisse verwechselt. Tats{\"a}chlich erweisen sich beide strittigen L{\"o}sungen als teilweise richtige Bestandteile der Gesamtl{\"o}sung. Die Argumentation wird in allgemeinverst{\"a}ndlicher Sprache gef{\"u}hrt und anschliessend durch eine formale mathematische Betrachtung erg{\"a}nzt.}, language = {de} } @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{FuegenschuhGeisslerGollmeretal., author = {F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Gollmer, Ralf and Hayn, Christine and Henrion, Rene and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Mirkov, Radoslava and Morsi, Antonio and R{\"o}misch, Werner and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Willert, Bernhard}, title = {Mathematical Optimization for Challenging Network Planning Problems in Unbundled Liberalized Gas Markets}, issn = {1438-0064}, doi = {10.1007/s12667-013-0099-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17821}, abstract = {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.}, language = {en} } @article{PfetschFuegenschuhGeissleretal., author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2014.888426}, abstract = {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 feasibility problem. The first phase consists of four distinct algorithms applying linear, and methods for complementarity constraints to compute possible settings for the discrete decisions. The second phase employs a precise continuous programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances that are significantly larger than networks that have appeared in the mathematical programming literature before.}, language = {en} } @article{FuegenschuhGeisslerGollmeretal., author = {F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Gollmer, Ralf and Hayn, Christine and Henrion, Ren{\´e} and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Mirkov, Radoslava and Morsi, Antonio and R{\"o}misch, Werner and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Willert, Bernhard}, title = {Mathematical optimization for challenging network planning problems in unbundled liberalized gas markets}, series = {Energy Systems}, volume = {5}, journal = {Energy Systems}, number = {3}, publisher = {Springer Berlin Heidelberg}, address = {Berlin}, doi = {10.1007/s12667-013-0099-8}, pages = {449 -- 473}, abstract = {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.}, language = {en} } @inproceedings{MartinGeisslerHeynetal.2011, author = {Martin, Alexander and Geißler, Bj{\"o}rn and Heyn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, series = {Optimierung in der Energiewirtschaft}, booktitle = {Optimierung in der Energiewirtschaft}, publisher = {VDI-Verlag, D{\"u}sseldorf}, pages = {105 -- 114}, year = {2011}, language = {en} } @misc{PfetschFuegenschuhGeissleretal., author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, issn = {1438-0064}, doi = {10.1080/10556788.2014.888426}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16531}, abstract = {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.}, language = {en} } @misc{MartinGeisslerHaynetal., author = {Martin, Alexander and Geißler, Bj{\"o}rn and Hayn, Christine and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Morsi, Antonio and Pfetsch, Marc and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Steinbach, Marc and Willert, Bernhard}, title = {Optimierung Technischer Kapazit{\"a}ten in Gasnetzen}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15121}, abstract = {Die mittel- und l{\"a}ngerfristige Planung f{\"u}r den Gastransport hat sich durch {\"A}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{\"a}t und Topologieplanung bezeichnet werden. Diese mathematischen Optimierungsprobleme werden vorgestellt und L{\"o}sungsans{\"a}tze skizziert.}, language = {de} }