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 - 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 - On PDE Solution in Transient Optimization of Gas Networks N2 - 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. T3 - ZIB-Report - 04-46 KW - Gas network KW - operative planning KW - PDE constrained optimization KW - KKT system factorization KW - sparse projection method Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8215 ER - TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Optimization Models for Operative Planning in Drinking Water Networks N2 - 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. T3 - ZIB-Report - 04-48 KW - Drinking water supply KW - distribution network KW - minimum cost operative planning KW - continuous time model KW - mixed integer model KW - nonlinear programming m Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8237 ER - TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Nonlinear Programming Techniques for Operative Planning in Large Drinking Water Networks N2 - 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. T3 - ZIB-Report - 05-31 KW - Water supply KW - large-scale nonlinear programming KW - convergence enhancement KW - discrete decisions KW - network reduction Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8657 ER - TY - GEN A1 - Burgschweiger, Jens A1 - Gnädig, Bernd A1 - Steinbach, Marc T1 - Optimierte Tagesplanung im Berliner Trinkwassernetz N2 - Der Artikel beschreibt ein mathematisches Optimierungssystem zur Betriebsplanung in großen Wassernetzen, das bei den Berliner Wasserbetrieben eingesetzt wird. Für das Berliner Versorgungsnetz werden Optimierungsergebnisse vorgestellt. T3 - ZIB-Report - 05-32 KW - Trinkwasserversorgung KW - kostenminimale Betriebsplanung KW - nichtlineare Optimierung KW - diskrete Entscheidungen Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8668 ER - TY - GEN A1 - Bley, Andreas A1 - Koch, Thorsten A1 - Niu, Lingfeng T1 - Experiments with nonlinear extensions to SCIP N2 - This paper describes several experiments to explore the options for solving a class of mixed integer nonlinear programming problems that stem from a real-world mine production planning project. The only type of nonlinear constraints in these problems are bilinear equalities involving continuous variables, which enforce the ratios between elements in mixed material streams. A branch-and-bound algorithm to handle the integer variables has been tried in another project. However, this branch-and-bound algorithm is not effective for handling the nonlinear constraints. Therefore state-of-the-art nonlinear solvers are utilized to solve the resulting nonlinear subproblems in this work. The experiments were carried out using the NEOS server for optimization. After finding that current nonlinear programming solvers seem to lack suitable preprocessing capabilities, we preprocess the instances beforehand and use an heuristic approach to solve the nonlinear subproblems. In the appendix, we explain how to add a polynomial constraint handler that uses IPOPT as embedded nonlinear programming solver for the constraint programming framework SCIP. This is one of the crucial steps for implementing our algorithm in SCIP. We briefly described our approach and give an idea of the work involved. T3 - ZIB-Report - 08-28 Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8300 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc T1 - Nonlinear pseudo-Boolean optimization: relaxation or propagation? N2 - Pseudo-Boolean problems lie on the border between satisfiability problems, constraint programming, and integer programming. In particular, nonlinear constraints in pseudo-Boolean optimization can be handled by methods arising in these different fields: One can either linearize them and work on a linear programming relaxation or one can treat them directly by propagation. In this paper, we investigate the individual strengths of these approaches and compare their computational performance. Furthermore, we integrate these techniques into a branch-and-cut-and-propagate framework, resulting in an efficient nonlinear pseudo-Boolean solver. T3 - ZIB-Report - 09-11 KW - Pseudo-Boolean KW - constraint integer programming KW - linear relaxation KW - separation algorithm KW - domain propagation Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11232 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Binary Quadratic Programming Approach to the Vehicle Positioning Problem N2 - The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view. T3 - ZIB-Report - 09-12 KW - quadratic programming KW - integer programming KW - nonlinear programming KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11242 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo A1 - Gleixner, Ambros T1 - Undercover – a primal heuristic for MINLP based on sub-MIPs generated by set covering N2 - We present Undercover, a primal heuristic for mixed-integer nonlinear programming (MINLP). The heuristic constructs a mixed-integer linear subproblem (sub-MIP) of a given MINLP by fixing a subset of the variables. We solve a set covering problem to identify a minimal set of variables which need to be fixed in order to linearise each constraint. Subsequently, these variables are fixed to approximate values, e.g. obtained from a linear outer approximation. The resulting sub-MIP is solved by a mixed-integer linear programming solver. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. Although general in nature, the heuristic seems most promising for mixed-integer quadratically constrained programmes (MIQCPs). We present computational results on a general test set of MIQCPs selected from the MINLPLib. T3 - ZIB-Report - 09-40 KW - MINLP KW - MIQCP KW - Primalheuristik KW - Nachbarschaftssuche KW - Mengenüberdeckung KW - mixed-integer nonlinear programming KW - MIQCP KW - primal heuristic KW - large neighborhood search KW - set covering Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11632 SN - 1438-0064 ER -