ICS »

Stream: Large scale optimization

Chair: Jacek Gondzio

1. How interior point methods can help vehicle routing
   Pedro Munari
   
   
   

   The applications of interior point methods (IPMs) have become incredibly diverse. The advantages of this clever class of methods go beyond linear and nonlinear programming. Indeed, several solution methods often used to solve combinatorial optimization problems can also take benefit from central solutions provided by IPMs. In this talk, we review the currently most successful strategies in this context and present the results of experiments with large-scale, real-life instances of vehicle routing problems, obtained from a case study developed with an oil company that operates in Brazil.
   
   

2. On unreduced KKT systems arising from Interior Point methods
   Benedetta Morini, Valeria Simoncini, Mattia Tani
   
   
   

   The focus of this talk is on the linear systems that arise from the application of Primal-Dual Interior Point methods to convex quadratic programming problems in standard form. The block structure of the matrices allows for formulations differing in their dimensions and spectral properties. We consider the unreduced 3x3 block linear systems and their symmetric and unsymmetric formulations and provide new spectral bounds. Then we present a theoretical and experimental analysis of the iterative solution of unreduced systems in the preconditioned regime.
   
   

3. Computing Null Space Operators in Linearly Constrained Programming
   Lukas Schork, Jacek Gondzio
   
   
   

   A method is described for finding a nonsingular submatrix of a rectangular matrix A. The method is based on LU factorization and is suitable when A is large and sparse. It uses theoretical results from rank revealing LU factorization to control the condition number of the submatrix even if A is ill conditioned. The method can be applied to obtain a stable null space operator of A or to compute constraint preconditioners for KKT systems. The numerical stability of the factors is vital in the context of interior point methods when highly ill conditioned systems are solved iteratively.
   
   

4. A distributed interior point method for multistage stochastic NLPs
   Marc Steinbach
   
   
   

   Interior point methods are well-suited for multistage stochastic NLPs if an efficient algorithm for the huge KKT system is available. For large scenario trees with a moderate number of node variables we present a distributed algorithm with low communication overhead using a static tree partitioning. We also address structured quasi-Newton updates and inertia corrections to handle non-convexity or rank-deficiency of the KKT system. Computational results for benchmark problems from portfolio optimization and robust model predictive control demonstrate the performance of our approach.