In the last 30 years optimization techniques experimented a dramatic advance, and nowadays they allow the efficient solution of convex problems of hundreds of thousands of variables and constraints. For mixed problems with binary variables the above dimensions significantly decrease. In the continuous case much of this success is due to developments in the field of interior point methods. However, the needs of the 21st century require the solution of much larger problems, such as those in worldwide logistics and production planning, data confidentiality or data mining. Some of these problems are intractable with current technologies. In previous projects the team developed a specialized interior point, considered among the most efficient for certain classes of structured problems. An implementation of this method, named BlockIP (http://www-eio.upc.edu/~jcastro/BlockIP.html) was released in 2014. Although designed for continuous optimization, it has recently been successfully applied within a cutting plane approach for mixed integer linear problems, being able to solve facility location instances of up to 600 binary and 600 million of continuous variables in less than an hour; such instances resulted intractable for the best optimization systems (e.g., CPLEX exhausted the (144 Gigabytes!) computer memory). Some recognized research centers, such as the the Zuse Institute Berlin (ZIB) are studying the use of BlockIP to solve very large-scale real problems obtained from industrial partners. This project focuses on both methodology and applications. Among the methodological objectives we find extensions to the specialized interior point method, such as: (1) Improving the preconditioned conjugate gradient used in BlockIP through an optimal combination of preconditioners. (2) Improving the hybrid preconditioner by power series and "splitting preconditioner" through new rules for computing the optimal basis in the "splitting preconditioner". (3) To study the suitability of BlockIP to unstructured problems, partitioning the constraints in two groups according to the principal angles of their subspaces. (4) Parallelization of BlockIP. We also find among the methodological objectives the development of cutting planes approaches for non-differentiable problems (which would allow the solution of mixed integer linear problems), using BlockIP for the solution of the subproblems. This will mean to study the use of inexact cuts and stabilization techniques in the "master" problem. In terms of applications, BlockIP will be used, either alone or within a cutting plane approach for, among others, the following problems: (1) Multicommodity network design with quadratic costs. (2) Solution of data protection problems using the method named "interval protection". (3) Solution of data protection problems in 1H2D and 3D tables using the method named controlled tabular adjustment, considering distances L1, L2 and pseudo-Huber. (3) Solution of stochastic, multiperiod, phase-in and phase-out facility location problems. (4) Real problems by ZIB (logistics, production planning). (5) Stochastic optimization problems.
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Programa Estatal de I+D+i Orientada a los Retos de la Sociedad
Retos de Investigación: Proyectos de I+D+i
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco