Network Flow Programming

Networks provide natural models for a variety of physical and organisation situations, including transport and distribution systems, assignment, precedence and paired comparisons. Most networks can be modelled, and hence optimised, using conventional Linear Programming (LP) algorithms, but in many cases the generality of LP represents modelling overkill.

By exploiting the simpler structure of networks it is possible to devise Network Flow Programming algorithms which are more economic of storage, more efficient in processing and substantially faster than LP. Like LP, this class of algorithms can be generalised to incorporate integer variables that represent major investment decisions.

One application of "Mixed Integer Network Flow Programming" is the depot or warehouse location problem. The problem involves supplying product to a geographically dispersed market, from one or more sources, via a network of transit depots. The cost of using a source or transit depot usually involves a fixed element. Finding an optimum supply network can be undertaken by offering "candidate" depots at major transportation nodes (often identified using a digital map) and submitting the problem to a Mixed Integer Network Flow Programming algorithm. The algorithm selects the subset of candidate depots whose total overhead cost provides the most economic supply network when added to the variable transportation and handling costs associated with it.

Network Flow Programming has been found to be of sufficient practical value to merit writing software. The first version was written in Pascal for MSDOS. Subsequent versions were translated in to C. A screen dump from the linear version of the Network Flow Programming engine is shown below:

NETWORK FLOW PROGRAMMING ALGORITHM:
C++ Version 3.0, May 31 1995

NODES: 400 ARCS: 1600 

Data input complete after 0 minutes and 0.22 seconds
Artificial basis generated after 0 minutes and 0.27 seconds
Feasible Solution found after 0 minutes and 0.98 seconds
Optimum Solution found after 0 minutes and 1.09 seconds
Solution Cost: 0
Solution file written after 0 minutes and 1.97 seconds
ALGORITHM STATUS: Complete

- ARC EXCHANGE -

ITERATION

IN:

OUT

POTENTIAL CHANGE

2179

-(18->9)

+(6->18)

2

DIAGNOSTICS:
ITERATION STATUS DESCRIPTION

(An example of the use of this algorithm is available here)

The success of a Depot Location program should be apparent from an inspection of isochrones centred at the selected depots. Alternatively a root and branch view should resemble a fan palm.