A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks
| Autor: | Jordi Castro, Stefano Nasini |
|---|---|
| Přispěvatelé: | Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa, Universitat Politècnica de Catalunya. GNOM - Grup d'Optimització Numèrica i Modelització |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Information Systems and Management
General Computer Science Computer science Minimum cost flow problems Diagonal 0211 other engineering and technologies MathematicsofComputing_NUMERICALANALYSIS 02 engineering and technology Interior-point methods Management Science and Operations Research Industrial and Manufacturing Engineering Separable space Quadratic equation 0502 economics and business 050210 logistics & transportation 021103 operations research 05 social sciences Matemàtiques i estadística [Àrees temàtiques de la UPC] Solver Flow network Large-scale optimization 90 Operations research mathematical programming [Classificació AMS] Nonlinear system Preconditioned conjugate gradient Modeling and Simulation Bipartite graph Node (circuits) Algorithm Interior point method Conjugate Cholesky decomposition |
| Zdroj: | UPCommons. Portal del coneixement obert de la UPC Universitat Politècnica de Catalunya (UPC) |
| Popis: | © 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|