An exterior simplex type algorithm for the minimum cost network flow problem

DOI10.1016/j.cor.2008.01.001zbMath1162.90547OpenAlexW2005630705WikidataQ57780945 ScholiaQ57780945MaRDI QIDQ958451

Konstantinos Paparrizos, Nikolaos Samaras, Angelo Sifaleras

Publication date: 4 December 2008

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2008.01.001

zbMATH Keywords

exterior point algorithmcombinatorial optimizationsimplex algorithmminimum cost network flow problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27) Extreme-point and pivoting methods (90C49) Experimental studies (91A90)

Related Items

Uncertain minimum cost flow problem, A nonlinear multiobjective bilevel model for minimum cost network flow problem in a large-scale construction project, A least-squares minimum-cost network flow algorithm, Exterior point simplex-type algorithms for linear and network optimization problems

Uses Software

• RelaxIV
• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An infeasible (exterior point) simplex algorithm for assignment problems
• A strongly polynomial minimum cost circulation algorithm
• Network generation using the Prufer code
• Use of dynamic trees in a network simplex algorithm for the maximum flow problem
• Finding minimum-cost flows by double scaling
• Applying steepest-edge techniques to a network primal-dual algorithm
• A polynomial time primal network simplex algorithm for minimum cost flows
• An efficient implementation of the network simplex method
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• A network simplex method
• New Finite Pivoting Rules for the Simplex Method
• A bad network problem for the simplex method and other minimum cost flow algorithms
• More pathological examples for network flow problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• On using exterior penalty approaches for solving linear programming problems