90C06 Large-scale problems
Refine
Year of publication
Document Type
- ZIB-Report (20)
- In Proceedings (1)
- Master's Thesis (1)
Language
- English (22)
Is part of the Bibliography
- no (22)
Keywords
- integer programming (3)
- semidefinite programming (3)
- KKT recursion (2)
- block structure (2)
- discrete dynamics (2)
- energy system models (2)
- high performance computing (2)
- interior-point method (2)
- linear programming (2)
- operative planning (2)
Institute
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.
Tree-Sparse Convex Programs
(2001)
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.
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.
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.
\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.
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.
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.
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.
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.
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.