Optimization Online


A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks

Jordi Castro (jordi.castro***at***upc.edu)
Stefano Nasini (s.nasini***at***ieseg.fr)

Abstract: 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.

Keywords: Interior-point methods ; Minimum cost flow problems ; Preconditioned conjugate gradient ; Large-scale optimization

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Network Optimization

Citation: J. Castro, S. Nasini, A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks, Research Report DR 2018/01, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2018.

Download: [PDF]

Entry Submitted: 11/30/2018
Entry Accepted: 11/30/2018
Entry Last Modified: 11/30/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society