Go to the content (press return)

Very large-scale optimization: methods and applications

Total activity: 18
Type of activity
Competitive project
Funding entity
Funding entity code
44.165,00 €
Start date
End date
Convex optimization, Optimización convexa, ciencia de datos, cutting plane methods, data protection, data science, facility location, interior point methods, localización de plantas, logistics, logística, mixed integer linear optimization, métodos de planos de corte, métodos de punto interior, optimización estocástica, optimización lineal entera mixta, problemas estructurados, protección de datos, stochastic optimization, structured problems
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.
Adm. Estat
Plan Estatal de Investigación Científica y Técnica y de Innovación 2013-2016
Call year
Funcding program
Programa Estatal de I+D+i Orientada a los Retos de la Sociedad
Funding call
Retos de Investigación: Proyectos de I+D+i
Grant institution
Gobierno De España. Ministerio De Economía Y Competitividad, Mineco


Scientific and technological production

1 to 18 of 18 results