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): 30
Encontrada(s) 1 página(s)

UPCommons. Portal del coneixement obert de la UPC
Publicación Contribución de congreso (ConferenceOutput)

An optimization-based decomposition heuristic for the microaggregation problem

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enrique
Given a set of points, the microaggregation problem aims to find a clustering with a minimum sum of squared errors (SSE), where the cardinality of each cluster is greater than or equal to k. Points in the cluster are replaced by the cluster centroid, thus satisfying k-anonymity. Microaggregation is considered one of the most effective techniques for numerical microdata protection. Traditionally, non-optimal solutions to the microaggregation problem are obtained by heuristic approaches. Recently, the authors of this paper presented a mixed integer linear optimization (MILO) approach based on column generation for computing tight solutions and lower bounds to the microaggregation problem. However, MILO can be computationally expensive for large datasets. In this work we present a new heuristic that combines three blocks: (1) a decomposition of the dataset into subsets, (2) the MILO column generation algorithm applied to each dataset in order to obtain a valid microaggregation, and (3) a local search improvement algorithm to get the final clustering. Preliminary computational results show that this approach was able to provide (and even improve upon) some of the best solutions (i.e., of smallest SSE) reported in the literature for the Tarragona and Census datasets, and k¿{3,5,10} ., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

A new interior-point approach for large separable convex quadratic 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., This work has been supported by the grants MINECO/FEDER MTM2015-65362-R andMCIU/AEI/FEDER RTI2018-097580-B-I00. The second author was supported by theCONACyT (Consejo Nacional de Ciencia y Tecnologia, México) grant CVU-394291. Wealso thank the two anonymous reviewers, whose suggestions and comments improved thequality of the paper., Peer Reviewed
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 Artículo científico (JournalArticle)

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
© The Author(s) 2022. Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature., 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., This research has been supported by the MCIN/AEI/FEDER project RTI2018-097580-B-I00., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Thirty years of optimization-based SDC methods for tabular data

  • Castro Pérez, Jordi|||0000-0003-3573-4568
In 1966 Bacharach published in Management Science a work on matrix rounding problems in two-way tables of economic statistics, formulated as a network optimization problem. This is likely the first application of optimization/operations research for statistical disclosure control (SDC) in tabular data. Years later, in 1982, Cox and Ernst used the same approach in a work in INFOR for a similar problem: controlled rounding. And thirty years ago, in 1992, a paper by Kelly, Golden and Assad appeared in Networks about the solution of the cell suppression problem, also using network optimization. Cell suppression was used for years as the main SDC technique for tabular data, and it was an active field of research which resulted in several lines of work and many publications. The above are some of the seminal works on the use of optimization methods for SDC when releasing tabular data. This paper discusses some of the research done this field since then, with a focus on the approaches that were of practical use. It also discusses their pros and cons compared to recent techniques that are not based on optimization methods., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

The Chebyshev center as an alternative to the analytic center in the feasibility pump

  • Baena Mirabete, Daniel
  • Castro Pérez, Jordi|||0000-0003-3573-4568
© The Author(s) 2023, As a heuristic for obtaining feasible points of mixed integer linear problems, the feasibility pump (FP) generates two sequences of points: one of feasible solutions for the relaxed linear problem; and another of integer points obtained by rounding the linear solutions. In a previous work, the present authors proposed a variant of FP, named analytic center FP, which obtains integer solutions by rounding points in the segment between the linear solution and the analytic center of the polyhedron of the relaxed problem. This work introduces a new FP variant that replaces the analytic center with the Chebyshev center. Two of the benefts of using the Chebyshev center are: (i) it requires the solution of a linear optimization problem (unlike the analytic center, which involves a convex nonlinear optimization problem for its exact solution); and (ii) it is invariant to redundant constraints (unlike the analytic center, which may not be well centered within the polyhedron for problems with highly rank-defcient matrices). The computational results obtained with a set of more than 200 MIPLIB2003 and MIPLIB2010 instances show that the Chebyshev center FP is competitive and can serve as an alternative to other FP variants., This research has been supported by the MCIN/AEI/FEDER project RTI2018-097580-B-I00. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

An algorithm for the microaggregation problem using column generation

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enric
The field of statistical disclosure control aims to reduce the risk of re-identifying an individual from disseminated data, a major concern among national statistical agencies. Operations Research (OR) techniques have been widely used in the past for protecting tabular data, but not microdata (i.e., files of individuals and attributes). Few papers apply OR techniques to the microaggregation problem, which is considered one of the best methods for microdata protection and 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. Using real data that is typically used in the literature, our computational results show, first, that solutions with small gaps are often achieved and, second, that dramatic improvements are obtained relative to the literature’s most popular heuristics., Author Enric Spagnolo-Arrizabalaga was supported by the ERASMUS+ Traineeship Program with a visiting period at CNR-IASI. Author Claudio Gentile was partly supported by the project PRIN 2015B5F27W funded by the Italian Ministry for Education, University, and Research; by the ITN 764759 “MINOA: Mixed-Integer Nonlinear Optimization Applications” of the European Union; and by the CNR Short-Term Mobility program CNRSTM14-PROT26328. Authors Jordi Castro and Claudio Gentile were supported by the MCIU/AEI/FEDER RTI2018-097580-B-I00 project of the Spanish Ministry of Science, Innovation and Universities., 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 Artículo científico (JournalArticle)

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

  • Castro Pérez, Jordi|||0000-0003-3573-4568
  • Escudero Bueno, Laureano F.
  • Monge Ivars, Juan Francisco
© 2023 The Authors. Published by Elsevier B.V, A novel approach based on a specialized interior-point method (IPM) is presented for solving largescale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees. This new solution approach considers a splitvariable formulation of the strategic and operational structures. The specialized IPM solves the normal equations 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 strategic-operational 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. Some of the most difficult instances of SND had 5 stages, 839 million linear variables, 13 million quadratic variables, 21 million constraints, and 3750 scenario tree nodes; while those of RM had 8 stages, 278 million linear variables, 100 million constraints, and 100,000 scenario tree nodes. For those problems, the proposed approach obtained the solution in 1.1 days using 174 gigabytes of memory for SND, and in 1.7 days using 83 gigabytes for RM; while CPLEX v20.1 required more than 53 days and 531 gigabytes for SND, and more than 19 days and 410 gigabytes for RM., J. Castro was supported by the MCIN/AEI/FEDER grant RTI2018-097580-B-I00. L.E. Escudero was supported by the MCIN/AEI/10.13039/501100011033 grant PID2021-122640OB-I00. J.F. Monge was supported by the MCIN/AEI/10.13039/501100011033/ERDF grants PID2019-105952GB-I00 and PID2021-122344NB-I00, and by PROMETEO/2021/063 grant funded by the government of the Valencia Community, Spain., Peer Reviewed
UPCommons. Portal del coneixement obert de la UPC
Publicación Artículo científico (JournalArticle)

Optimal postponement in supply chain network design under uncertainty: an application for additive manufacturing

  • Ramón Lumbierres, Daniel Jacobo|||0000-0002-3353-4266
  • Heredia, F.-Javier (Francisco Javier)|||0000-0003-4613-957X
  • Minguella Canela, Joaquim|||0000-0002-0552-1687
  • Muguruza Blanco, Asier
This study presents a new two-stage stochastic programming decision model for assessing how to introduce some new manufacturing technology into any generic supply and distribution chain. It additionally determines the optimal degree of postponement, as represented by the so-called customer order decoupling point (CODP), while assuming uncertainty in demand for multiple products. To this end, we propose here the formulation of a generic supply chain through an oriented graph that represents all the deployable alternative technologies, which are defined through a set of operations that are characterized by lead times and cost parameters. Based on this graph, we develop a mixed integer two-stage stochastic program that finds the optimal manufacturing technology for meeting each market’s demand, each operation’s optimal production quantity, and each selected technology’s optimal CODP. We also present and analyse a case study for introducing additive manufacturing technologies., This work was developed under an Accenture Open Innovation University [grant number I-01326] and was also partially supported by grant RTI2018-097580-B-I00 of the Ministry of Economy and Competitiveness of Spain., 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)

Critical evaluation of European balancing markets to enable the participation of Demand Aggregators

  • Barbero, Mattia
  • Corchero García, Cristina|||0000-0002-8465-0830
  • Canals Casals, Lluc|||0000-0002-4791-9917
  • Igualada González, Lucía|||0000-0001-7718-5283
  • Heredia, F.-Javier (Francisco Javier)|||0000-0003-4613-957X
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, European Directives are incentivizing consumers to play an active role in the electricity system and to collaborate to maintain its stability, which has been historically provided by large generation power plants. However, it is not easy for the System Operator to handle the coexistence of consumers and generators in the same markets. Under these circumstances, a new actor allows small residential and commercial consumers to participate in flexibility markets: The Demand Aggregator. However, balancing markets opened to Demand Aggregators still present several barriers that do not allow their practical participation. This study analyzes barriers and enablers of four European electricity markets and proposes a new market framework that would enhance Demand Aggregators’ participation. To validate the proposed market and to understand the economic potentials of aggregated small tertiary buildings, a Demand Aggregator is simulated using real building’s consumption data. Results show that technical requirements to participate in balancing markets such as the minimum bid size, the symmetricity of the offer and the product resolution strongly affect incomes for Demand Aggregators. However, neither in the proposed market, the creation of a Demand Aggregator whose business model is focused on small tertiary buildings does not seem realistic due to low incomes in comparison to the fixed costs necessary to enable Demand Response, especially if only the air conditioning system is considered., 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 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.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

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

  • Castro Pérez, Jordi
  • Escudero Bueno, Laureano F.
  • Monge Ivars, Juan Francisco
© 2023 The Authors. Published by Elsevier B.V, A novel approach based on a specialized interior-point method (IPM) is presented for solving largescale stochastic multistage continuous optimization problems, which represent the uncertainty in strategic multistage and operational two-stage scenario trees. This new solution approach considers a splitvariable formulation of the strategic and operational structures. The specialized IPM solves the normal equations 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 strategic-operational 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. Some of the most difficult instances of SND had 5 stages, 839 million linear variables, 13 million quadratic variables, 21 million constraints, and 3750 scenario tree nodes; while those of RM had 8 stages, 278 million linear variables, 100 million constraints, and 100,000 scenario tree nodes. For those problems, the proposed approach obtained the solution in 1.1 days using 174 gigabytes of memory for SND, and in 1.7 days using 83 gigabytes for RM; while CPLEX v20.1 required more than 53 days and 531 gigabytes for SND, and more than 19 days and 410 gigabytes for RM., J. Castro was supported by the MCIN/AEI/FEDER grant RTI2018-097580-B-I00. L.E. Escudero was supported by the MCIN/AEI/10.13039/501100011033 grant PID2021-122640OB-I00. J.F. Monge was supported by the MCIN/AEI/10.13039/501100011033/ERDF grants PID2019-105952GB-I00 and PID2021-122344NB-I00, and by PROMETEO/2021/063 grant funded by the government of the Valencia Community, Spain., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

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

  • Castro Pérez, Jordi
© The Author(s) 2022. Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature., 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., This research has been supported by the MCIN/AEI/FEDER project RTI2018-097580-B-I00., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

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

  • Castro Pérez, Jordi
  • Lama Zubirán, Paula de la
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., This work has been supported by the grants MINECO/FEDER MTM2015-65362-R andMCIU/AEI/FEDER RTI2018-097580-B-I00. The second author was supported by theCONACyT (Consejo Nacional de Ciencia y Tecnologia, México) grant CVU-394291. Wealso thank the two anonymous reviewers, whose suggestions and comments improved thequality of the paper., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

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

  • Castro Pérez, Jordi
  • 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, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

The Chebyshev center as an alternative to the analytic center in the feasibility pump

  • Baena Mirabete, Daniel
  • Castro Pérez, Jordi
© The Author(s) 2023, As a heuristic for obtaining feasible points of mixed integer linear problems, the feasibility pump (FP) generates two sequences of points: one of feasible solutions for the relaxed linear problem; and another of integer points obtained by rounding the linear solutions. In a previous work, the present authors proposed a variant of FP, named analytic center FP, which obtains integer solutions by rounding points in the segment between the linear solution and the analytic center of the polyhedron of the relaxed problem. This work introduces a new FP variant that replaces the analytic center with the Chebyshev center. Two of the benefts of using the Chebyshev center are: (i) it requires the solution of a linear optimization problem (unlike the analytic center, which involves a convex nonlinear optimization problem for its exact solution); and (ii) it is invariant to redundant constraints (unlike the analytic center, which may not be well centered within the polyhedron for problems with highly rank-defcient matrices). The computational results obtained with a set of more than 200 MIPLIB2003 and MIPLIB2010 instances show that the Chebyshev center FP is competitive and can serve as an alternative to other FP variants., This research has been supported by the MCIN/AEI/FEDER project RTI2018-097580-B-I00. Funding Open Access funding provided thanks to the CRUE-CSIC agreement with Springer Nature, Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

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

  • Castro Pérez, Jordi
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, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación

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

  • Castro Pérez, Jordi
  • Lama Zubirán, Paula de la
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, Preprint
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

An algorithm for the microaggregation problem using column generation

  • Castro Pérez, Jordi
  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enric
The field of statistical disclosure control aims to reduce the risk of re-identifying an individual from disseminated data, a major concern among national statistical agencies. Operations Research (OR) techniques have been widely used in the past for protecting tabular data, but not microdata (i.e., files of individuals and attributes). Few papers apply OR techniques to the microaggregation problem, which is considered one of the best methods for microdata protection and 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. Using real data that is typically used in the literature, our computational results show, first, that solutions with small gaps are often achieved and, second, that dramatic improvements are obtained relative to the literature’s most popular heuristics., Author Enric Spagnolo-Arrizabalaga was supported by the ERASMUS+ Traineeship Program with a visiting period at CNR-IASI. Author Claudio Gentile was partly supported by the project PRIN 2015B5F27W funded by the Italian Ministry for Education, University, and Research; by the ITN 764759 “MINOA: Mixed-Integer Nonlinear Optimization Applications” of the European Union; and by the CNR Short-Term Mobility program CNRSTM14-PROT26328. Authors Jordi Castro and Claudio Gentile were supported by the MCIU/AEI/FEDER RTI2018-097580-B-I00 project of the Spanish Ministry of Science, Innovation and Universities., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Contribución de congreso (ConferenceOutput)

An optimization-based decomposition heuristic for the microaggregation problem

  • Castro Pérez, Jordi
  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enrique
Given a set of points, the microaggregation problem aims to find a clustering with a minimum sum of squared errors (SSE), where the cardinality of each cluster is greater than or equal to k. Points in the cluster are replaced by the cluster centroid, thus satisfying k-anonymity. Microaggregation is considered one of the most effective techniques for numerical microdata protection. Traditionally, non-optimal solutions to the microaggregation problem are obtained by heuristic approaches. Recently, the authors of this paper presented a mixed integer linear optimization (MILO) approach based on column generation for computing tight solutions and lower bounds to the microaggregation problem. However, MILO can be computationally expensive for large datasets. In this work we present a new heuristic that combines three blocks: (1) a decomposition of the dataset into subsets, (2) the MILO column generation algorithm applied to each dataset in order to obtain a valid microaggregation, and (3) a local search improvement algorithm to get the final clustering. Preliminary computational results show that this approach was able to provide (and even improve upon) some of the best solutions (i.e., of smallest SSE) reported in the literature for the Tarragona and Census datasets, and k¿{3,5,10} ., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Thirty years of optimization-based SDC methods for tabular data

  • Castro Pérez, Jordi
In 1966 Bacharach published in Management Science a work on matrix rounding problems in two-way tables of economic statistics, formulated as a network optimization problem. This is likely the first application of optimization/operations research for statistical disclosure control (SDC) in tabular data. Years later, in 1982, Cox and Ernst used the same approach in a work in INFOR for a similar problem: controlled rounding. And thirty years ago, in 1992, a paper by Kelly, Golden and Assad appeared in Networks about the solution of the cell suppression problem, also using network optimization. Cell suppression was used for years as the main SDC technique for tabular data, and it was an active field of research which resulted in several lines of work and many publications. The above are some of the seminal works on the use of optimization methods for SDC when releasing tabular data. This paper discusses some of the research done this field since then, with a focus on the approaches that were of practical use. It also discusses their pros and cons compared to recent techniques that are not based on optimization methods., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Critical evaluation of European balancing markets to enable the participation of Demand Aggregators

  • Barbero, Mattia
  • Corchero García, Cristina
  • Canals Casals, Lluc
  • Igualada González, Lucía
  • Heredia, F.-Javier (Francisco Javier)
© 2020. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/, European Directives are incentivizing consumers to play an active role in the electricity system and to collaborate to maintain its stability, which has been historically provided by large generation power plants. However, it is not easy for the System Operator to handle the coexistence of consumers and generators in the same markets. Under these circumstances, a new actor allows small residential and commercial consumers to participate in flexibility markets: The Demand Aggregator. However, balancing markets opened to Demand Aggregators still present several barriers that do not allow their practical participation. This study analyzes barriers and enablers of four European electricity markets and proposes a new market framework that would enhance Demand Aggregators’ participation. To validate the proposed market and to understand the economic potentials of aggregated small tertiary buildings, a Demand Aggregator is simulated using real building’s consumption data. Results show that technical requirements to participate in balancing markets such as the minimum bid size, the symmetricity of the offer and the product resolution strongly affect incomes for Demand Aggregators. However, neither in the proposed market, the creation of a Demand Aggregator whose business model is focused on small tertiary buildings does not seem realistic due to low incomes in comparison to the fixed costs necessary to enable Demand Response, especially if only the air conditioning system is considered., Peer Reviewed, Postprint (author's final draft)
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Optimal postponement in supply chain network design under uncertainty: an application for additive manufacturing

  • Ramón Lumbierres, Daniel Jacobo
  • Heredia, F.-Javier (Francisco Javier)
  • Minguella Canela, Joaquim
  • Muguruza Blanco, Asier
This study presents a new two-stage stochastic programming decision model for assessing how to introduce some new manufacturing technology into any generic supply and distribution chain. It additionally determines the optimal degree of postponement, as represented by the so-called customer order decoupling point (CODP), while assuming uncertainty in demand for multiple products. To this end, we propose here the formulation of a generic supply chain through an oriented graph that represents all the deployable alternative technologies, which are defined through a set of operations that are characterized by lead times and cost parameters. Based on this graph, we develop a mixed integer two-stage stochastic program that finds the optimal manufacturing technology for meeting each market’s demand, each operation’s optimal production quantity, and each selected technology’s optimal CODP. We also present and analyse a case study for introducing additive manufacturing technologies., This work was developed under an Accenture Open Innovation University [grant number I-01326] and was also partially supported by grant RTI2018-097580-B-I00 of the Ministry of Economy and Competitiveness of Spain., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publicación

An algorithm for the microaggregation problem using column generation

  • Gentile, Claudio
  • Spagnolo Arrizabalaga, Enric
  • Castro Pérez, Jordi
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., Preprint
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)