Skip to main content

OPTIMIZACION DE PROBLEMAS ESTRUCTURADOS DE GRAN ESCALA. APLICACIONES A CONFIDENCIALIDAD DE DATOS.

MTM2012-31440

•
Funding agency name Ministerio de Economía y Competitividad
Funding agency acronym MINECO
Program Programa Nacional de Proyectos de Investigación Fundamental
Subprogram Subprograma de Proyectos de Investigación Fundamental no Orientada
Call Proyectos I+D
Call year 2012
State Plan 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Management unit Secretaría de Estado de Investigación, Desarrollo e Innovación
Beneficiary centre UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

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

Interior-point solver for convex separable block-angular problems

  • Castro Pérez, Jordi|||0000-0003-3573-4568
Constraints matrices with block-angular structures are pervasive in optimization. Interior-point methods have shown to be competitive for these structured problems by exploiting the linear algebra. One of these approaches solves the normal equations using sparse Cholesky factorizations for the block constraints, and a reconditioned conjugate gradient (PCG) for the linking constraints. The preconditioner is based on a power series expansion which approximates the inverse of the matrix of the linking constraints system. In this work, we present an efficient solver based on this algorithm. Some of its features are as follows: it solves linearly constrained convex separable problems (linear, quadratic or nonlinear); both Newton and second-order predictor–corrector directions can be used, either with the Cholesky+PCG scheme or with a Cholesky factorization of normal equations; the preconditioner may include any number of terms of the power series; for any number of these terms, it estimates the spectral radius of the matrix in the power series (which is instrumental for the quality of the preconditioner). The solver has been hooked to the structure-conveying modelling language (SML) based on the popular AMPL modeling language. Computational results are reported for some large and/or difficult instances in the literature: (1) multicommodity flow problems; (2) minimum congestion problems; (3) statistical data protection problems using and distances (which are linear and quadratic problems, respectively), and the pseudo-Huber function, a nonlinear approximation to which improves the preconditioner. In the largest instances, of up to 25 millions of variables and 300,000 constraints, this approach is from 2 to 3 orders of magnitude faster than state-of-the-art linear and quadratic optimization solvers., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

Mathematical programming approaches for classes of random network problems

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Nasini, Stefano
Random simulations from complicated combinatorial sets are often needed in many classes of stochastic problems. This is particularly true in the analysis of complex networks, where researchers are usually interested in assessing whether an observed network feature is expected to be found within families of networks under some hypothesis (named conditional random networks, i.e., networks satisfying some linear constraints). This work presents procedures to generate networks with specified structural properties which rely on the Solution of classes of integer optimization problems. We show that, for many of them, the constraints matrices are totally unimodular, allowing the efficient generation of conditional random networks by specialized interior-point methods. The computational results suggest that the proposed methods can represent a general framework for the efficient generation of random networks even beyond the models analyzed in this paper. This work also opens the posSibility for other applications of mathematical programming in the analysis of complex networks. (C) 2015 Elsevier B.V. All rights reserved., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Artículo científico (JournalArticle)

A mathematical programming approach for different scenarios of bilateral bartering

  • Nasini, Stefano
  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Fonseca Casas, Pau|||0000-0002-6747-9736
The analysis of markets with indivisible goods and fixed exogenous prices has played an important role in economic models, especially in relation to wage rigidity and unemployment. This paper provides a novel mathematical programming based approach to study pure exchange economies where discrete amounts of commodities are exchanged at fixed prices. Barter processes, consisting in sequences of elementary reallocations of couple of commodities among couples of agents, are formalized as local searches converging to equilibrium allocations. A direct application of the analysed processes in the context of computational economics is provided, along with a Java implementation of the described approaches., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Using BCD-CTA for difficult tables: a practical experiment with a real Eurostat table

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • González Alastrué, José Antonio|||0000-0002-3113-4779
  • Hundepool, Anco
CTA is a post-tabular perturbative approach for statistical disclosure control. Its purpose is to compute the closest safe table to the original data, using some distance. Sensitive cells are adjusted either upwards or downwards (binary decision), and the resulting cells have to be accordingly (and minimally) modi_ed to preserve marginals. For real and large tables, CTA may result in a dicult mixed integer linear problem for some weights in the objective function. In those situations the Block Coordinate Descent (BCD) heuristic for CTA|which is included in the Tau-Argus CTA distribution|may be used to quickly obtain a feasible, hopefully close to optimality, solution. We present a practical experiment using a large and di_cult real-world table from Eurostat. We will show that, for unitary weights, while the standard CTA can not obtain a solution in about half an hour, the BCD-CTA approach provides a solution in few seconds., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Estudio, informe, memoria (Report)

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

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Nasini, Stefano
J. Castro, S. Nasini, On geometrical properties of preconditioners in IPMs for classes of block-angular problems, Research Report DR 2016/03, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2016., 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 constraints structure. In particular, it is seen that 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 127 million of variables and up to 7.5 million of constraints is also presented
Recercat. Dipósit de la Recerca de Catalunya
Publication

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

  • Castro Pérez, Jordi
  • Nasini, Stefano
J. Castro, S. Nasini, On geometrical properties of preconditioners in IPMs for classes of block-angular problems, Research Report DR 2016/03, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2016., 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 constraints structure. In particular, it is seen that 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 127 million of variables and up to 7.5 million of constraints is also presented, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

A mathematical programming approach for different scenarios of bilateral bartering

  • Nasini, Stefano
  • Castro Pérez, Jordi
  • Fonseca Casas, Pau
The analysis of markets with indivisible goods and fixed exogenous prices has played an important role in economic models, especially in relation to wage rigidity and unemployment. This paper provides a novel mathematical programming based approach to study pure exchange economies where discrete amounts of commodities are exchanged at fixed prices. Barter processes, consisting in sequences of elementary reallocations of couple of commodities among couples of agents, are formalized as local searches converging to equilibrium allocations. A direct application of the analysed processes in the context of computational economics is provided, along with a Java implementation of the described approaches., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Interior-point solver for convex separable block-angular problems

  • Castro Pérez, Jordi
Constraints matrices with block-angular structures are pervasive in optimization. Interior-point methods have shown to be competitive for these structured problems by exploiting the linear algebra. One of these approaches solves the normal equations using sparse Cholesky factorizations for the block constraints, and a reconditioned conjugate gradient (PCG) for the linking constraints. The preconditioner is based on a power series expansion which approximates the inverse of the matrix of the linking constraints system. In this work, we present an efficient solver based on this algorithm. Some of its features are as follows: it solves linearly constrained convex separable problems (linear, quadratic or nonlinear); both Newton and second-order predictor–corrector directions can be used, either with the Cholesky+PCG scheme or with a Cholesky factorization of normal equations; the preconditioner may include any number of terms of the power series; for any number of these terms, it estimates the spectral radius of the matrix in the power series (which is instrumental for the quality of the preconditioner). The solver has been hooked to the structure-conveying modelling language (SML) based on the popular AMPL modeling language. Computational results are reported for some large and/or difficult instances in the literature: (1) multicommodity flow problems; (2) minimum congestion problems; (3) statistical data protection problems using and distances (which are linear and quadratic problems, respectively), and the pseudo-Huber function, a nonlinear approximation to which improves the preconditioner. In the largest instances, of up to 25 millions of variables and 300,000 constraints, this approach is from 2 to 3 orders of magnitude faster than state-of-the-art linear and quadratic optimization solvers., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Using BCD-CTA for difficult tables: a practical experiment with a real Eurostat table

  • Castro Pérez, Jordi
  • González Alastrué, José Antonio
  • Hundepool, Anco
CTA is a post-tabular perturbative approach for statistical disclosure control. Its purpose is to compute the closest safe table to the original data, using some distance. Sensitive cells are adjusted either upwards or downwards (binary decision), and the resulting cells have to be accordingly (and minimally) modi_ed to preserve marginals. For real and large tables, CTA may result in a dicult mixed integer linear problem for some weights in the objective function. In those situations the Block Coordinate Descent (BCD) heuristic for CTA|which is included in the Tau-Argus CTA distribution|may be used to quickly obtain a feasible, hopefully close to optimality, solution. We present a practical experiment using a large and di_cult real-world table from Eurostat. We will show that, for unitary weights, while the standard CTA can not obtain a solution in about half an hour, the BCD-CTA approach provides a solution in few seconds., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Mathematical programming approaches for classes of random network problems

  • Castro Pérez, Jordi
  • Nasini, Stefano
Random simulations from complicated combinatorial sets are often needed in many classes of stochastic problems. This is particularly true in the analysis of complex networks, where researchers are usually interested in assessing whether an observed network feature is expected to be found within families of networks under some hypothesis (named conditional random networks, i.e., networks satisfying some linear constraints). This work presents procedures to generate networks with specified structural properties which rely on the Solution of classes of integer optimization problems. We show that, for many of them, the constraints matrices are totally unimodular, allowing the efficient generation of conditional random networks by specialized interior-point methods. The computational results suggest that the proposed methods can represent a general framework for the efficient generation of random networks even beyond the models analyzed in this paper. This work also opens the posSibility for other applications of mathematical programming in the analysis of complex networks. (C) 2015 Elsevier B.V. All rights reserved., Peer Reviewed, Postprint (author's final draft)