Solving Large-Scale Real-World Minimum-Cost Flow Problems by a Network Simplex Method

Please always quote using this URN: urn:nbn:de:0297-zib-2184
  • This paper presents a large-scale real-world application of the minimum-cost flow problem, describes some details of a new implementation of the network simplex algorithm, and reports on computational comparisions. The real-world test sets include minimum-cost flow problems that are based on single-depot vehicle scheduling problems and on a Lagrangean relaxation of multiple-depot vehicle scheduling problems. Some of the problems are extremely large with up to 42,000 nodes and 20,000,000 arcs. The standard test problems are generated with NETGEN and include parts of the DIMACS standard problems. Our network simplex code is compared with \mbox{RELAX-IV}, Cost Scaling 2 version 3.4, and CPLEX's network solver NETOPT.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Löbel
Document Type:ZIB-Report
Date of first Publication:1996/02/29
Series (Serial Number):ZIB-Report (SC-96-07)