Loading...
Loading...

Go to the content (press return)

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

Author
Castro, J.; Nasini, S.
Type of activity
Journal article
Journal
European journal of operational research
Date of publication
2021-05
Volume
290
Number
3
First page
857
Last page
869
DOI
10.1016/j.ejor.2020.10.027
Project funding
Modelling and optimization of large-scale structured problems and applications
Repository
http://hdl.handle.net/2117/351220 Open in new window
http://www-eio.upc.edu/~jcastro/publications/reports/dr2018-01.pdf Open in new window
URL
https://www.sciencedirect.com/science/article/abs/pii/S0377221720309036 Open in new window
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 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, quadra...
Citation
Castro, J.; Nasini, S. A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks. "European journal of operational research", Maig 2021, vol. 290, núm. 3, p. 857-869.
Keywords
Interior-point methods, Large-scale optimization, Minimum cost flow problems, Preconditioned conjugate gradient
Group of research
GNOM - Mathematical Optimization Group

Participants