Search

Research Report UPC-DEIO DR 2018-01. November 2018 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 apply 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). 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 and 200 and five million nodes in each subset of the node partition. 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 it never exhausted the 192 Gigabytes of memory of the server used for the runs. For assignment problems the network algorithms in LEMON were the most efficient option.

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

The thesis deals with the theoretical and practical study of mathematical programming methodologies to the analysis complex networks and their application in economic and social problems. More specifically, it applies models and methods for solving linear and integer programming problems to network models exploiting the matrix structure of such models, resulting in efficient computational procedures and small processing time. As a consequence, it allows the study of larger and more complex networks models that arise in many economical and sociological applications. The main efforts have been addressed to the development of a rigorous mathematical programming based framework, which is able to capture many classes of complex network problems. Such a framework involves a general and flexible modeling approach, based on linear and integer programmin, as well as a collection of efficient probabilistic procedures to deal with these models. The computer implementation has been carried out by high level programming languages, such as Java, MatLab, R and AMPL. The final chapter of the thesis introduced an extension of the analyzed model to the case of microeconomic interaction, providing a fruitful mathematical linkage between its optimization-like properties and its multi-agents properties. The theoretical and practical use of optimization methods represents the trait-de-union of the different chapters. The overall structure of the thesis manuscript contains three parts: Part I: The fine-grained structure of complex networks: theories, models and methods; Chapter 1 and Chapter 2. Part II: Mathematical Programming based approaches for random models of network formation; Chapter 3, Chapter 4 and Chapter 5. Part III: Strategic models of network formation. Chapter 6. Results of this research have generated four working papers in quality scientific journals: one has been accepted and three are under review. Some results have been also presented in four international conferences., La tesis aborda el estudio teórico y práctico de las metodologías de programación matemática para el análisis de redes complejas y su aplicación a problemas económicos y sociales. Más específicamente, se aplica modelos y métodos para resolver problemas de programación lineal y de programación lineal entera explotando las estructuras matriciales de tales modelos, lo que resulta en procedimientos computacionales eficientes y bajo coste de procesamiento. Como consecuencia de ello, las metodologías propuestas permiten el estudio de modelos complejos de gran dimensión, para redes complejas que surgen en muchas aplicaciones económicas y sociológicas. Los principales esfuerzos se han dirigido al desarrollo de un marco teórico basado en la programación matemática, que es capaz de capturar muchas clases de problemas de redes complejas. Dicho marco teórico envuelve un sistema general y flexible de modelado y una colección de procedimientos probabilísticos para solucionar eficientemente dichos modelos, basados en la programación linear y entera. Las implementaciones informáticas se han llevado a cabo mediante lenguajes de programación de alto nivel, como Java, Matlab, R y AMPL. El último capítulo de la tesis introduce una extensión de los modelos analizados, para el caso de la interacción microeconómica, con el objetivo de establecer un nexo metodológico entre sus propiedades de optimización y sus propiedades multi-agentes. El uso teórico y práctico de los métodos de optimización representa el elemento de conjunción de los distintos capítulos. Parte I: The fine-grained structure of complex networks: theories, models and methods; - Capitulo 1 y Capitulo 2. Parte II: Mathematical Programming based approaches for random models of network formation; - Capitulo 3, Capitulo 4 y Capitulo 5. Parte III: Strategic models of network formation. - Capitulo 6. Los resultados de esta investigación han generado cuatro papers en revistas científicas indexadas: uno ha sido aceptado, tres están en revisión. Algunos resultados han sido también presentados en cuatro conferencias internacionales

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.

The analysis of markets with indivisible goods and xed 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 xed 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 analyzed processes in the context of computational economics is provided, along with a Java implementation of the approaches described in this paper: http://www-eio.upc.edu/~nasini/SER/launch.html

Network analysis is of great interest for the study of social , biological and technolog- ical networks, with applications, among others, in busines s, marketing, epidemiology and telecommunications. Researchers are often interested in a ssessing whether an observed fea- ture in some particular network is expected to be found withi n families of networks under some hypothesis (named conditional random networks, i.e., networks satisfying some linear constraints). This work presents procedures to generate ne tworks with specified structural properties which rely on the solution of classes of integer o ptimization problems. We show that, for many of them, the constraints matrices are totally unimodular, allowing the efficient generation of conditional random networks by polynomial ti me interior-point methods. The computational results suggest that the proposed methods ca n represent a general framework for the efficient generation of random networks even beyond the models analyzed in this pa- per. This work also opens the possibility for other applicat ions of mathematical programming in the analysis of complex networks.

Complex networks is a recent area of research motivated by the empirical study of realworld networks, such as social relations, protein interaction, neuronal connections, etc. As closed-form probabilistic models of networks are often not available, the ability of randomly generating networks verifying specific constraints might be useful. The purpose of this work is to develop optimization-based procedures to randomly generate networks with structural constraints, within the probabilistic framework of conditional uniform models. Based on the characterization of families of networks by means of systems of linear constraints, polynomialtime methods to generate networks with specified structural properties are constructed.

Aquest Treball de finalització de Master proposa mètodes de programació matemàtica, en particular de programació lineal, per atacar el problema de la simulació de xarxes aleatòries amb restriccions. El resultat principal obtingut en aquest treball ha estat la possibilitat de caracteritzar determinades famílies de xarxes aleatòries mitjançant sistemes de restriccions lineals amb una estructura matricial particularment interessant des d'una perspectiva de mètodes numèrics. Els resultats computacionals mostren com els mètodes proposats poden representar un marc de treball general per a la simulació eficient de xarxes aleatòries The goal is to obtain optimization-based procedures for the generation of conditional random networks. The firstpart would consist on the algebraic characterization of families of networks by linear systems constrained to the nonnegative orthant. This should enable the construction of polynomial-time procedures togenerate instances of networks with specified structural properties, based on interior-point methods for Linear Programming

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 effect 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. This approach 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, outperforming other stateof- the-art methods, which exhausted the (144 Gigabytes of) available memory in the largest instances.