TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Martin, Alexander T1 - MIPLIB 2003 N2 - This paper reports on the fourth version of the Mixed Integer Programming Library. Since ({\sc miplib}) is to provide a concise set of challenging problems, it became necessary to purge instances that became too easy. We present an overview of the 27 new problems and statistical data for all 60 instances. T3 - ZIB-Report - 05-28 KW - Mathematical Programming KW - Mixed Integer Programming KW - IP KW - MIP KW - Optimization KW - Instances Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8625 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 - Froyland, Gary A1 - Koch, Thorsten A1 - Megow, Nicole A1 - Duane, Emily A1 - Wren, Howard T1 - Optimizing the Landside Operation of a Container Terminal N2 - This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas. A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most~8\% above a lower bound on optimal RMG utilization. T3 - ZIB-Report - 06-06 KW - Integer Programming KW - Container Terminal KW - Intermediate Storage Area KW - Landside operation KW - Yard crane scheduling KW - Storage space allocation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9004 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 - CHAP A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method T2 - Operations Research Proceedings 2019 N2 - In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2020 U6 - https://doi.org/10.1007/978-3-030-48439-2_13 SP - 105 EP - 111 PB - Springer International Publishing ET - 1 ER - TY - THES A1 - Gleixner, Ambros T1 - Solving Large-scale Open Pit Mining Production Scheduling Problems by Integer Programming N2 - Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of Möhring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05% gap of the optimum. Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11389 ER - TY - GEN A1 - Gleixner, Ambros A1 - Kempke, Nils-Christian A1 - Koch, Thorsten A1 - Rehfeldt, Daniel A1 - Uslu, Svenja T1 - First Experiments with Structure-Aware Presolving for a Parallel Interior-Point Method N2 - In linear optimization, matrix structure can often be exploited algorithmically. However, beneficial presolving reductions sometimes destroy the special structure of a given problem. In this article, we discuss structure-aware implementations of presolving as part of a parallel interior-point method to solve linear programs with block-diagonal structure, including both linking variables and linking constraints. While presolving reductions are often mathematically simple, their implementation in a high-performance computing environment is a complex endeavor. We report results on impact, performance, and scalability of the resulting presolving routines on real-world energy system models with up to 700 million nonzero entries in the constraint matrix. T3 - ZIB-Report - 19-39 KW - block structure KW - energy system models KW - interior-point method KW - high performance computing KW - linear programming KW - parallelization KW - presolving KW - preprocessing Y1 - 2019 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-74084 SN - 1438-0064 ER - TY - GEN A1 - Helmberg, Christoph T1 - SBmethod --- A C++ Implementation of the Spectral Bundle Method. Manual to Version 1.1 N2 - \texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables $y_i$ may be sign constrained, $C$ and and $A_i$ are given real symmetric matrices, $b\in\mathbf{R}^m$ allows to specify a linear cost term, and $a>0$ is a constant multiplier for the maximum eigenvalue function $\lambda_{\max}(\cdot)$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode. T3 - ZIB-Report - 00-35 KW - semidefinite programming KW - semidefinite relaxations KW - spectral bundle method KW - eigenvalue optimization KW - large-scale problems Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6039 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 - Helmberg, Christoph A1 - Kiwiel, K.C. T1 - A Spectral Bundle Method with Bounds N2 - Semidefinite relaxations of quadratic 0-1 programming or graph partitioning problems are well known to be of high quality. However, solving them by primal-dual interior point methods can take much time even for problems of moderate size. The recent spectral bundle method of Helmberg and Rendl can solve quite efficiently large structured equality-constrained semidefinite programs if the trace of the primal matrix variable is fixed, as happens in many applications. We extend the method so that it can handle inequality constraints without seriously increasing computation time. Encouraging preliminary computational results are reported. T3 - ZIB-Report - SC-99-37 KW - Eigenvalue optimization KW - convex optimization Y1 - 1999 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4256 ER - TY - GEN A1 - Helmberg, Christoph A1 - Röhl, Stefan T1 - A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses N2 - For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream. T3 - ZIB-Report - 05-11 KW - convex relaxation KW - integer programming KW - stochastic demand KW - network models KW - large scale problems KW - bundle method KW - logistics KW - vehicle routing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8454 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 - 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 - 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 - GEN A1 - Helmberg, Christoph T1 - Numerical Evaluation of SBmethod N2 - We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7$^{th}$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming. T3 - ZIB-Report - 01-37 KW - semidefinite programming KW - large scale methods KW - computational KW - semidefinite relaxations Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6637 ER - TY - GEN A1 - Helmberg, Christoph T1 - A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations N2 - The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably. T3 - ZIB-Report - 01-26 KW - bisection KW - equicut KW - max-cut KW - semidefinite programming KW - spectral bundle method KW - subgradient method KW - quadratic 0-1 programming Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6527 ER - TY - GEN A1 - Koch, Thorsten A1 - Ralphs, Ted A1 - Shinano, Yuji T1 - What could a million CPUs do to solve Integer Programs? N2 - Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise the question of whether best practices in sequential solution of ILPs will be effective in massively parallel environments. T3 - ZIB-Report - 11-40 Y1 - 2011 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-14222 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Set Partitioning Approach to Shunting N2 - The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems. T3 - ZIB-Report - 09-18 KW - integer programming KW - set partitioning KW - combinatorial packing KW - vehicle positioning Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11326 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Sagnol, Guillaume A1 - Schlechte, Thomas A1 - Swarat, Elmar T1 - Optimal Toll Enforcement - an Integration of Vehicle Routing and Duty Rostering N2 - We present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method. T3 - ZIB-Report - 13-79 KW - vehicle routing KW - crew rostering KW - integer programming KW - bicriteria optimization Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-45107 SN - 1438-0064 ER -