Andrew Goldberg's Network Optimization Library
Andrew Goldberg's Network Optimization Library
The following software is available.
The software is designed to run under UNIX/LINUX. It also runs under
Cygwin on Windows (some programs may require slight modifications).
Check copyright information before downloading the software.
A license may be required.
The software comes with no warranty, expressed of implied.

CS2 contains an efficient implementation of a scaling
pushrelabel algorithm for the minimumcost flow/transportation problems.
For a detailed description and experimental data, see
"An Efficient Implementation of a Scaling MinimumCost Flow Algorithm"
by A. V. Goldberg,
J. Algorithms 22 (1997), pages 129.
Written in C.
Available from
IG Systems.

paraF contains an implementation of an efficient parametric
flow algorithm.
For a detailed description and experimental data, see
"Experimental Evaluation of a Parametric Flow Algorithm"
by M. Babenko and A. V. Goldberg,
Microsoft Research Technical Report MSRTR200677 2006.
Written in C++.
Available from
Microsoft Research.

HIPR is a new, more robust version of
the hilevel variant of the PRF code h_prf (see below).
In most cases, we recommend the
new code over the old one.
Written in C. The current version is 3.7.
Copyright /
HIPR (tar format).

PRF contains an efficient implementations the pushrelabel
method for the maximum flow/minimum cut problems.
For a detailed description and experimental data, see
"On Implementing PushRelabel Method for the Maximum Flow Problem,"
Algorithmica 19 (1997), 390  410.
In most cases, we recommend the
new code, HI_PR, over the old one.
Written in C. The current version is 1.8.
Copyright /
PRF (tar format).

MLB contains efficient implementations of the multilevel bucket
and smart queue algorithms for the singlesource shortest path problem with
nonnegative integral arc lengths.
It also contains problem generators.
For a detailed describtion and experimental data, see
"Shortest Path Algorithms: Engineering Aspects"
by A. V. Goldberg, proceedings of the
International Symposium on Algorithms and Computation (ISAAC '01),
Springer Lecture Notes in Computer Science (2001), and
"A Simple Shortest Path Algorithm with Linear Average Time"
by A. V. Goldberg, proceedings of the
9th European Symposium on Algorithms (ESA '01),
Springer Lecture Notes in Computer Science LNCS 2161 (2001),
pages 230241.
Written in C++. The current version is 2.1.
Copyright /
MLB (tar format).

MINCUTLIB Contains codes and data sets for the minimum cut problem.
For a detailed description and experimental data, see
"Experimental Study of Minimum Cut Algorithms,"
C. S. Chekuri, A. V. Goldberg, D. R. Karger,M. S. Levine, and C. Stein,
Technical Report 96132,
NEC Research Institute, Inc., 1996,
Copyright /
MINCUTLIB home page.

BIM contains codes, generators, and generator inputs for
bipartite matching and unit capacity flow algorithms.
For a detailed description and experimental data, see our paper
"Augment or Push? A computational study of Bipartite Matching and
Unit Capacity Flow Algorithms,"
NEC Research Institute TR #98036R , 1998.
Copyright /
BIM (compressed tar format).

SPLIB contains codes, generators, and generator inputs for
shortest path algorithms.
For a detailed description and experimental data, see
"Shortest Paths Algorithms: Theory and Experimental Evaluation,"
by B.V. Cherkassky, A.V. Goldberg, and T. Radzik,
Math. Prog. 73 (1996), pages 129174.
Copyright /
SPLIB (tar format).

SPC contains codes, generators, and generator inputs for
shortest path algorithms with negative cycle detection.
For a detailed description and experimental data, see
"NegativeCycle Detection Algorithms,"
B. V. Cherkassky and A. V. Goldberg,
Technical Report 96029, NEC Research Institute, Inc., 1996.
Copyright /
SPC (tar format).

CSA contains an efficient implementation of a scaling pushrelabel
algorithm for the assignment problem.
For a detailed description and experimental data, see
"An Efficient Cost Scaling Algorithm for the Assignment Problem,"
Math. Prog. 71 (1995), pages 153178.
Copyright /
CSA version 1.2.1 (compressed tar).

HQ contains implementations of Dijkstra's shortest path
algorithm based on hot queue, multilevel buckets, and kheap data
structures, as well as problem generators.
For a detailed description and experimental data, see
"Buckets, Heaps, Lists, and Monotone Priority Queues,"
B.V. Cherkassky, A.V. Goldberg, and C. Silverstein, Technical Report 96070,
NEC Research Institute, Inc., 1996,
"Implementations of Dijkstra's Algorithm Based on MultiLevel Buckets,"
A.V. Goldberg, and C. Silverstein, Technical Report 95187,
NEC Research Institute, Inc., 1995.
Copyright /
HQ (tar format).
Number of visitors since 1/1/02: