An Implementation of the Dual Affine Scaling Algorithm for Minimum-Cost Flow on Bipartite Uncapacitated Networks

DOI10.1137/0803025zbMath0794.90014OpenAlexW2045721235MaRDI QIDQ3140000

Geraldo Veiga, Mauricio G. C. Resende

Publication date: 6 December 1993

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0803025

zbMATH Keywords

interior point algorithmminimum-cost flowdual affine scaling algorithmbipartite uncapacitated networkspreconditional conjugate gradient algorithmrandomly generated assignment problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05) Deterministic network models in operations research (90B10) Iterative numerical methods for linear systems (65F10) Discrete location and assignment (90B80) Parallel numerical computation (65Y05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Improving an interior-point algorithm for multicommodity flows by quadratic regularizations ⋮ Descent direction algorithm with multicommodity flow problem for signal optimization and traffic assignment jointly ⋮ Fuzzy goal programming: complementary slackness conditions and computational schemes ⋮ Unnamed Item ⋮ An interior-point approach for primal block-angular problems ⋮ Prim-based support-graph preconditioners for min-cost flow problems ⋮ Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods ⋮ Some concepts of the fuzzy multicommodity flow problem and their application in fuzzy network design ⋮ Gigaflops in linear programming ⋮ On Geometrical Properties of Preconditioners in IPMs for Classes of Block-Angular Problems ⋮ Interior point methods 25 years later ⋮ Solving scalarized multi-objective network flow problems using an interior point method ⋮ Sparsity preserving preconditioners for linear systems in interior-point methods ⋮ Fortran subroutines for network flow optimization using an interior point algorithm ⋮ Experiments with a hybrid interior point/combinatorial approach for network flow problems ⋮ A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks ⋮ Interior-point solver for convex separable block-angular problems ⋮ Convergence analysis of the inexact infeasible interior-point method for linear optimization ⋮ Implementation of interior-point methods for LP based on Krylov subspace iterative solvers with inner-iteration preconditioning ⋮ Improving an interior-point approach for large block-angular problems by hybrid preconditioners

Uses Software

• KORBX
• MINOS
• NETGEN
• RELAX4