Pasar al contenido principal

OPTIMIZACION DE MUY GRAN ESCALA: METODOS Y APLICACIONES

MTM2015-65362-R

•
Nombre agencia financiadora Ministerio de Economía y Competitividad
Acrónimo agencia financiadora MINECO
Programa Programa Estatal de I+D+i Orientado a los Retos de la Sociedad
Convocatoria Proyectos I+D+i Retos de Investigación
Año convocatoria 2015
Plan Estatal 2013-2016 Plan Estatal de Investigación Científica y Técnica y de Innovación
Unidad de gestión Dirección General de Investigación Científica y Técnica
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA
Identificador persistente http://dx.doi.org/10.13039/501100003329

Resultados relacionados

Resultados totales (Incluyendo duplicados): 20
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A linear optimization based method for data privacy in statistical tabular data

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • González Alastrué, José Antonio|||0000-0002-3113-4779
National Statistical Agencies routinely disseminate large amount of data. Prior to dissemination these data have to be protected to avoid releasing confidential information. Controlled tabular adjustment (CTA) is one of the available methods for this purpose. CTA formulates an optimization problem that looks for the safe table which is closest to the original one. The standard CTA approach results in a mixed integer linear optimization (MILO) problem, which is very challenging for current technology. In this work we present a much less costly variant of CTA that formulates a multiobjective linear optimization (LO) problem, where binary variables are pre-fixed, and the resulting continuous problem is solved by lexicographic optimization. Extensive computational results are reported using both commercial (CPLEX and XPRESS) and open source (Clp) solvers, with either simplex or interior-point methods, on a set of real instances. Most instances were successfully solved with the LO-CTA variant in less than one hour, while many of them are computationally very expensive with the MILO-CTA formulation. The interior-point method outperformed simplex in this particular application., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Nasini, Stefano
  • Saldanha da Gama, Francisco
We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling conditions and problem specifications on the computational performance are also investigated both theoretically and empirically, providing a deeper understanding of the significant factors influencing the overall efficiency of the cutting-plane method. The methodology proposed allowed the solution of instances of up to 200 potential locations, one million customers and three periods, resulting in mixed integer linear optimization problems of up to 600 binary and 600 millions of continuous variables. Those problems were solved by the specialized approach in less than one hour and a half, outperforming other state-of-the-art methods, which exhausted the (144 Gigabytes of) available memory in the largest instances., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

A linear optimization based method for data privacy in statistical tabular data

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • González Alastrué, José Antonio|||0000-0002-3113-4779
National Statistical Agencies routinely disseminate large amounts of data. Prior to dissemination these data have to be protected to avoid releasing confidential information. Controlled tabular adjustment (CTA) is one of the available methods for this purpose. CTA formulates an optimization problem that looks for the safe table which is closest to the original one. The standard CTA approach results in a mixed integer linear optimization (MILO) problem, which is very challenging for current technology. In this work we present a much less costly variant of CTA that formulates a multiobjective linear optimization (LO) problem, where binary variables are pre-fixed, and the resulting continuous problem is solved by lexicographic optimization. Extensive computational results are reported using both commercial (CPLEX and XPRESS) and open source (Clp) solvers, with either simplex or interior-point methods, on a set of real instances. Most instances were successfully solved with the LO-CTA variant in less than one hour, while many of them are computationally very expensive with the MILO-CTA formulation. The interior-point method outperformed simplex in this particular application., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

A second order cone formulation of continuous CTA model

  • Lesaja, Goran
  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Oganian, Anna
The final publication is available at link.springer.com, In this paper we consider a minimum distance Controlled Tabular Adjustment (CTA) model for statistical disclosure limitation (control) of tabular data. The goal of the CTA model is to find the closest safe table to some original tabular data set that contains sensitive information. The measure of closeness is usually measured using l1 or l2 norm; with each measure having its advantages and disadvantages. Recently, in [4] a regularization of the l1 -CTA using Pseudo-Huber func- tion was introduced in an attempt to combine positive characteristics of both l1 -CTA and l2 -CTA. All three models can be solved using appro- priate versions of Interior-Point Methods (IPM). It is known that IPM in general works better on well structured problems such as conic op- timization problems, thus, reformulation of these CTA models as conic optimization problem may be advantageous. We present reformulation of Pseudo-Huber-CTA, and l1 -CTA as Second-Order Cone (SOC) op- timization problems and test the validity of the approach on the small example of two-dimensional tabular data set., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Stabilized Benders methods for large-scale combinatorial optimization, with application to data privacy

  • Baena, Daniel
  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Frangioni, Antonio
The Cell Suppression Problem (CSP) is a very large Mixed-IntegerLinear Problem arising in statistical disclosure control. However, CSPhas the typical structure that allows application of the Benders de-composition, which is known to suffer from oscillation and slow con-vergence, compounded with the fact that the master problem is com-binatorial. To overcome this drawback we present a stabilized Bendersdecomposition whose master is restricted to a neighborhood of success-ful candidates by local branching constraints, which are dynamicallyadjusted, and even dropped, during the iterations. Our experimentswith synthetic and real-world instances with up to 24000 binary vari-ables, 181M continuous variables and 367M constraints show that ourapproach is competitive with both the current state-of-the-art code forCSP, and the Benders implementation in CPLEX 12.7. In some in-stances, stabilized Benders provided a very good solution in less thanone minute, while the other approaches found no feasible solution inone hour., This work has been supported by MINECO–FEDER grant MTM2015-65362-R., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Nasini, Stefano
© 2020 Elsevier, The computation of the Newton direction is the most time consuming step of interior-point methods. This direction was efficiently computed by a combination of Cholesky factorizations and conjugate gradients in a specialized interior-point method for block-angular structured problems. In this work we refine this algorithmic approach to solve very large instances of minimum cost flows problems in bipartite networks, for convex objective functions with diagonal Hessians (i.e., either linear, quadratic or separable nonlinear objectives). For this class of problems the specialized algorithm only required the solution of a system by conjugate gradients at each interior-point iteration, avoiding Cholesky factorizations. After analyzing the theoretical properties of the interior-point method for this kind of problems, we provide extensive computational experiments with linear and quadratic instances of up to one billion arcs (corresponding to 200 nodes and five million nodes in each subset of the node partition, respectively). For linear and quadratic instances our approach is compared with the barriers algorithms of CPLEX (both standard path-following and homogeneous-self-dual); for linear instances it is also compared with the different algorithms of the state-of-the-art network flow solver LEMON (namely: network simplex, capacity scaling, cost scaling and cycle canceling). The specialized interior-point approach significantly outperformed the other approaches in most of the linear and quadratic transportation instances tested. In particular, it always provided a solution within the time limit; and (like LEMON, and unlike CPLEX) it never exhausted the memory of the server used for the runs. For assignment problems the network algorithms in LEMON were the most efficient option., This work has been supported by the grants MINECO /FEDER MTM2015-65362-R and MCIU/ AEI /FEDER RTI2018-097580-B-I00, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

On geometrical properties of preconditioners in IPMs for classes of block-angular problems

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Nasini, Stefano
One of the most efficient interior-point methods for some classes of block-angular structured problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. In this work we show that the choice of a good preconditioner depends on geometrical properties of the constraint structure. In particular, the principal angles between the subspaces generated by the diagonal blocks and the linking constraints can be used to estimate ex ante the efficiency of the preconditioner. Numerical validation is provided with some generated optimization problems. An application to the solution of multicommodity network flow problems with nodal capacities and equal flows of up to 64 million variables and up to 7.9 million constraints is also presented. These computational results also show that predictor-corrector directions combined with iterative system solves can be a competitive option for large instances., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Symmetric vs asymmetric protection levels in SDC methods for tabular data

  • Baena, Daniel
  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • González Alastrué, José Antonio|||0000-0002-3113-4779
The final publication is available at link.springer.com, Protection levels on sensitive cells—which are key parameters of any statistical disclosure control method for tabular data—are related to the difficulty of any attacker to recompute a good estimation of the true cell values. Those protection levels are two numbers (one for the lower protection, the other for the upper protection) imposing a safety interval around the cell value, that is, no attacker should be able to recompute an estimate within such safety interval. In the symmetric case the lower and upper protection levels are equal; otherwise they are referred as asymmetric protection levels. In this work we empirically study the effect of symmetry in protection levels for three protection methods: cell suppression problem (CSP), controlled tabular adjustment (CTA), and interval protection (IP). Since CSP and CTA are mixed integer linear optimization problems, it is seen that the symmetry (or not) of protection levels affect to the CPU time needed to compute a solution. For IP, a linear optimization problem, it is observed that the symmetry heavily affects to the quality of the solution provided rather than to the solution time., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Using interior point solvers for optimizing progressive lens models with spherical coordinates

  • Casanellas Peñalver, Glòria|||0000-0002-3790-0665
  • Castro Pérez, Jordi|||0000-0003-3573-4568
This is a post-peer-review, pre-copyedit version of an article published in Optimization and engineering. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11081-019-09480-z, Designing progressive lenses is a complex problem that has been previously solved by formulating an optimization model based on Cartesian coordinates. This work presents a new progressive lens model using spherical coordinates, and interior point solvers are used to solve this new optimization model. Although this results in a highly nonlinear, nonconvex, continuous optimization problem, the new spherical coordinates model exhibits better convexity properties compared to previous ones based on Cartesian coordinates. The real-world instances considered result in nonlinear optimization problems of about 900 variables and 15,000 constraints. Each constraint corresponds to a point on the grid that defines the lens surface. The number of variables depends on the precision of the B-spline basis used for representing the surface; and the number of constraints depends on the shape and quality of the design. We present our results for progressive lenses, which were obtained using the AMPL modeling language and the nonlinear interior point solvers IPOPT, LOQO and KNITRO. The computational results are reported, as well as some examples of real-world progressive lenses that were calculated using this new model. In terms of quality, the progressive lenses obtained by our model are competitive with those of previous models used for commercial eyeglasses., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publicación

A linear optimization based method for data privacy in statistical tabular data

  • Castro Pérez, Jordi
  • González Alastrué, José Antonio
National Statistical Agencies routinely disseminate large amounts of data. Prior to dissemination these data have to be protected to avoid releasing confidential information. Controlled tabular adjustment (CTA) is one of the available methods for this purpose. CTA formulates an optimization problem that looks for the safe table which is closest to the original one. The standard CTA approach results in a mixed integer linear optimization (MILO) problem, which is very challenging for current technology. In this work we present a much less costly variant of CTA that formulates a multiobjective linear optimization (LO) problem, where binary variables are pre-fixed, and the resulting continuous problem is solved by lexicographic optimization. Extensive computational results are reported using both commercial (CPLEX and XPRESS) and open source (Clp) solvers, with either simplex or interior-point methods, on a set of real instances. Most instances were successfully solved with the LO-CTA variant in less than one hour, while many of them are computationally very expensive with the MILO-CTA formulation. The interior-point method outperformed simplex in this particular application., Peer Reviewed, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Symmetric vs asymmetric protection levels in SDC methods for tabular data

  • Baena, Daniel
  • Castro Pérez, Jordi
  • González Alastrué, José Antonio
The final publication is available at link.springer.com, Protection levels on sensitive cells—which are key parameters of any statistical disclosure control method for tabular data—are related to the difficulty of any attacker to recompute a good estimation of the true cell values. Those protection levels are two numbers (one for the lower protection, the other for the upper protection) imposing a safety interval around the cell value, that is, no attacker should be able to recompute an estimate within such safety interval. In the symmetric case the lower and upper protection levels are equal; otherwise they are referred as asymmetric protection levels. In this work we empirically study the effect of symmetry in protection levels for three protection methods: cell suppression problem (CSP), controlled tabular adjustment (CTA), and interval protection (IP). Since CSP and CTA are mixed integer linear optimization problems, it is seen that the symmetry (or not) of protection levels affect to the CPU time needed to compute a solution. For IP, a linear optimization problem, it is observed that the symmetry heavily affects to the quality of the solution provided rather than to the solution time., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A cutting-plane approach for large-scale capacitated multi-period facility location using a specialized interior-point method

  • Castro Pérez, Jordi
  • Nasini, Stefano
  • Saldanha da Gama, Francisco
We propose a cutting-plane approach (namely, Benders decomposition) for a class of capacitated multi-period facility location problems. The novelty of this approach lies on the use of a specialized interior-point method for solving the Benders subproblems. The primal block-angular structure of the resulting linear optimization problems is exploited by the interior-point method, allowing the (either exact or inexact) efficient solution of large instances. The consequences of different modeling conditions and problem specifications on the computational performance are also investigated both theoretically and empirically, providing a deeper understanding of the significant factors influencing the overall efficiency of the cutting-plane method. The methodology proposed allowed the solution of instances of up to 200 potential locations, one million customers and three periods, resulting in mixed integer linear optimization problems of up to 600 binary and 600 millions of continuous variables. Those problems were solved by the specialized approach in less than one hour and a half, outperforming other state-of-the-art methods, which exhausted the (144 Gigabytes of) available memory in the largest instances., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Using interior point solvers for optimizing progressive lens models with spherical coordinates

  • Casanellas Peñalver, Glòria
  • Castro Pérez, Jordi
This is a post-peer-review, pre-copyedit version of an article published in Optimization and engineering. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11081-019-09480-z, Designing progressive lenses is a complex problem that has been previously solved by formulating an optimization model based on Cartesian coordinates. This work presents a new progressive lens model using spherical coordinates, and interior point solvers are used to solve this new optimization model. Although this results in a highly nonlinear, nonconvex, continuous optimization problem, the new spherical coordinates model exhibits better convexity properties compared to previous ones based on Cartesian coordinates. The real-world instances considered result in nonlinear optimization problems of about 900 variables and 15,000 constraints. Each constraint corresponds to a point on the grid that defines the lens surface. The number of variables depends on the precision of the B-spline basis used for representing the surface; and the number of constraints depends on the shape and quality of the design. We present our results for progressive lenses, which were obtained using the AMPL modeling language and the nonlinear interior point solvers IPOPT, LOQO and KNITRO. The computational results are reported, as well as some examples of real-world progressive lenses that were calculated using this new model. In terms of quality, the progressive lenses obtained by our model are competitive with those of previous models used for commercial eyeglasses., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

A second order cone formulation of continuous CTA model

  • Lesaja, Goran
  • Castro Pérez, Jordi
  • Oganian, Anna
The final publication is available at link.springer.com, In this paper we consider a minimum distance Controlled Tabular Adjustment (CTA) model for statistical disclosure limitation (control) of tabular data. The goal of the CTA model is to find the closest safe table to some original tabular data set that contains sensitive information. The measure of closeness is usually measured using l1 or l2 norm; with each measure having its advantages and disadvantages. Recently, in [4] a regularization of the l1 -CTA using Pseudo-Huber func- tion was introduced in an attempt to combine positive characteristics of both l1 -CTA and l2 -CTA. All three models can be solved using appro- priate versions of Interior-Point Methods (IPM). It is known that IPM in general works better on well structured problems such as conic op- timization problems, thus, reformulation of these CTA models as conic optimization problem may be advantageous. We present reformulation of Pseudo-Huber-CTA, and l1 -CTA as Second-Order Cone (SOC) op- timization problems and test the validity of the approach on the small example of two-dimensional tabular data set., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A linear optimization based method for data privacy in statistical tabular data

  • Castro Pérez, Jordi
  • González Alastrué, José Antonio
National Statistical Agencies routinely disseminate large amount of data. Prior to dissemination these data have to be protected to avoid releasing confidential information. Controlled tabular adjustment (CTA) is one of the available methods for this purpose. CTA formulates an optimization problem that looks for the safe table which is closest to the original one. The standard CTA approach results in a mixed integer linear optimization (MILO) problem, which is very challenging for current technology. In this work we present a much less costly variant of CTA that formulates a multiobjective linear optimization (LO) problem, where binary variables are pre-fixed, and the resulting continuous problem is solved by lexicographic optimization. Extensive computational results are reported using both commercial (CPLEX and XPRESS) and open source (Clp) solvers, with either simplex or interior-point methods, on a set of real instances. Most instances were successfully solved with the LO-CTA variant in less than one hour, while many of them are computationally very expensive with the MILO-CTA formulation. The interior-point method outperformed simplex in this particular application., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Stabilized Benders methods for large-scale combinatorial optimization, with application to data privacy

  • Baena, Daniel
  • Castro Pérez, Jordi
  • Frangioni, Antonio
The Cell Suppression Problem (CSP) is a very large Mixed-IntegerLinear Problem arising in statistical disclosure control. However, CSPhas the typical structure that allows application of the Benders de-composition, which is known to suffer from oscillation and slow con-vergence, compounded with the fact that the master problem is com-binatorial. To overcome this drawback we present a stabilized Bendersdecomposition whose master is restricted to a neighborhood of success-ful candidates by local branching constraints, which are dynamicallyadjusted, and even dropped, during the iterations. Our experimentswith synthetic and real-world instances with up to 24000 binary vari-ables, 181M continuous variables and 367M constraints show that ourapproach is competitive with both the current state-of-the-art code forCSP, and the Benders implementation in CPLEX 12.7. In some in-stances, stabilized Benders provided a very good solution in less thanone minute, while the other approaches found no feasible solution inone hour., This work has been supported by MINECO–FEDER grant MTM2015-65362-R., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

  • Castro Pérez, Jordi
  • Nasini, Stefano
© 2020 Elsevier, The computation of the Newton direction is the most time consuming step of interior-point methods. This direction was efficiently computed by a combination of Cholesky factorizations and conjugate gradients in a specialized interior-point method for block-angular structured problems. In this work we refine this algorithmic approach to solve very large instances of minimum cost flows problems in bipartite networks, for convex objective functions with diagonal Hessians (i.e., either linear, quadratic or separable nonlinear objectives). For this class of problems the specialized algorithm only required the solution of a system by conjugate gradients at each interior-point iteration, avoiding Cholesky factorizations. After analyzing the theoretical properties of the interior-point method for this kind of problems, we provide extensive computational experiments with linear and quadratic instances of up to one billion arcs (corresponding to 200 nodes and five million nodes in each subset of the node partition, respectively). For linear and quadratic instances our approach is compared with the barriers algorithms of CPLEX (both standard path-following and homogeneous-self-dual); for linear instances it is also compared with the different algorithms of the state-of-the-art network flow solver LEMON (namely: network simplex, capacity scaling, cost scaling and cycle canceling). The specialized interior-point approach significantly outperformed the other approaches in most of the linear and quadratic transportation instances tested. In particular, it always provided a solution within the time limit; and (like LEMON, and unlike CPLEX) it never exhausted the memory of the server used for the runs. For assignment problems the network algorithms in LEMON were the most efficient option., This work has been supported by the grants MINECO /FEDER MTM2015-65362-R and MCIU/ AEI /FEDER RTI2018-097580-B-I00, Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

On geometrical properties of preconditioners in IPMs for classes of block-angular problems

  • Castro Pérez, Jordi
  • Nasini, Stefano
One of the most efficient interior-point methods for some classes of block-angular structured problems solves the normal equations by a combination of Cholesky factorizations and preconditioned conjugate gradient for, respectively, the block and linking constraints. In this work we show that the choice of a good preconditioner depends on geometrical properties of the constraint structure. In particular, the principal angles between the subspaces generated by the diagonal blocks and the linking constraints can be used to estimate ex ante the efficiency of the preconditioner. Numerical validation is provided with some generated optimization problems. An application to the solution of multicommodity network flow problems with nodal capacities and equal flows of up to 64 million variables and up to 7.9 million constraints is also presented. These computational results also show that predictor-corrector directions combined with iterative system solves can be a competitive option for large instances., Peer Reviewed, Postprint (author's final draft)