Pasar al contenido principal

MODELIZACION Y OPTIMIZACION DE PROBLEMAS ESTRUCTURADOS DE GRAN ESCALA Y APLICACIONES

RTI2018-097580-B-I00

•
Nombre agencia financiadora Agencia Estatal de Investigación
Acrónimo agencia financiadora AEI
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 2018
Plan Estatal 2017-2020 Plan Estatal de Investigación Científica y Técnica y de Innovación
Centro beneficiario UNIVERSITAT POLITECNICA DE CATALUNYA

Resultados relacionados

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

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

On solving large-scale multistage stochastic problems with a new specialized interior-point approach

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Escudero Bueno, Laureano F.
  • Monge Ivars, Juan Francisco
A novel approach based on a specialized interior-point method (IPM) is presented for solving large-scale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees, the latter being rooted at the strategic nodes. This new solution approach considers a split-variable formulation of the strategic and operational structures, for which copies are made of the strategic nodes and the structures are rooted in the form of nested strategic-operational two-stage trees. The specialized IPM solves the normal equations of the problem’s Newton system by combining Cholesky factorizations with preconditioned conjugate gradients, doing so for, respectively, the constraints of the stochastic formulation and those that equate the split-variables. We show that, for multistage stochastic problems, the preconditioner (i) is a block-diagonal matrix composed of as many shifted tridiagonal matrices as the number of nested strategicoperational two-stage trees, thus allowing the efficient solution of systems of equations; (ii) its complexity in a multistage stochastic problem is equivalent to that of a very large-scale two-stage problem. A broad computational experience is reported for large multistage stochastic supply network design (SND) and revenue management (RM) problems; the mathematical structures vary greatly for those two application types. Some of the most difficult instances of SND had 5 stages, 839 million variables, 13 million quadratic variables, 21 million constraints, and 3750 scenario tree nodes; while those of RM had 8 stages, 278 million variables, 100 million constraints, and 100,000 scenario tree nodes. For those problems, the proposed approach obtained the solution in 2.3 days using 167 gigabytes of memory for SND, and in 1.7 days using 83 gigabytes for RM; while the state-of-the-art solver CPLEX v20.1 required more than 24 days and 526 gigabytes for SND, and more than 19 days and 410 gigabytes for RM, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

A new interior-point approach for large two-stage stochastic problems

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Lama Zubirán, Paula de la|||0000-0001-5735-9581
Two-stage stochastic models give rise to very large optimization problems. Several approaches havebeen devised for efficiently solving them, including interior-point methods (IPMs). However, usingIPMs, the linking columns associated to first-stage decisions cause excessive fill-in for the solutionof the normal equations. This downside is usually alleviated if variable splitting is applied to first-stage variables. This work presents a specialized IPM that applies variable splitting and exploits thestructure of the deterministic equivalent of the stochastic problem. The specialized IPM combinesCholesky factorizations and preconditioned conjugate gradients for solving the normal equations.This specialized IPM outperforms other approaches when the number of first-stage variables is largeenough. This paper provides computational results for two stochastic problems: (1) a supply chainsystem and (2) capacity expansion in an electric system. Both linear and convex quadratic formu-lations were used, obtaining instances of up to 38 million variables and six million constraints. Thecomputational results show that our procedure is more efficient than alternative state-of-the-art IPMimplementations (e.g., CPLEX) and other specialized solvers for stochastic optimization, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

New interior-point approach for one- and two-class linear support vector machines using multiple variable splitting

  • Castro Pérez, Jordi|||0000-0003-3573-4568
Multiple variable splitting is a general technique for decomposing problems by using copies of variables and additional linking constraints that equate their values. The resulting large optimization problem can be solved with a specialized interior-point method that exploits the problem structure and computes the Newton direction with a combination of direct and iterative solvers (i.e., Cholesky factorizations and preconditioned conjugate gradients for linear systems related to, respectively, subproblems and new linking constraints). The present work applies this method to solving real-world binary classification and novelty (or outlier) detection problems by means of, respectively, two-class and one-class linear support vector machines (SVMs). Unlike previous interior-point approaches for SVMs, which were practical only with low-dimensional points, the new proposal can also deal with high-dimensional data. The new method is compared with state-of-the-art solvers for SVMs, that are based on either interior-point algorithms (such as SVM-OOPS) or specific algorithms developed by the machine learning community (such as LIBSVM and LIBLINEAR). The computational results show that, for two-class SVMs, the new proposal is competitive not only against previous interior-point methods—and much more efficient than they are with high-dimensional data—but also against LIBSVM; whereas LIBLINEAR generally outperformed the proposal. For one-class SVMs, the new method consistently outperformed all other approaches, in terms of either solution time or solution quality, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Estudio, informe, memoria (Report)

An algorithm for the microaggregation problem using column generation

  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enric
  • Castro Pérez, Jordi|||0000-0003-3573-4568
The field of Statistical Disclosure Control aims at reducing the risk of re-identification of an individualwhen disseminating data, and it is one of the main concerns of national statistical agencies. OperationsResearch (OR) techniques were widely used in the past for the protection of tabular data, but not formicrodata (i.e., files of individuals and attributes). This work presents (as far as we know, for the firsttime) an application of OR techniques for the microaggregation problem, which is considered one thebest methods for microdata protection and it is known to be NP-hard.The new heuristic approach is based on a column generation scheme and, unlike previous (primal)heuristics for microaggregation, it also provides a lower bound on the optimal microaggregation. Com-putational results on real data typically used in the literature show that solutions with small gaps areoften achieved and that dramatic improvements are obtained with respect to the most popular heuristicsin the literature.