The NETFLOW Procedure

## Mathematical Description of NPSC

If a network programming problem with side constraints has n nodes, a arcs, g nonarc variables, and k side constraints, then the formal statement of the problem solved by PROC NETFLOW is
min {cT x + dT z}

subject to
F x = b   where
c is the a x 1 objective function coefficient of arc variables vector (the cost vector)
x is the a x 1 arc variable value vector (the flow vector)
d is the g x 1 objective function coefficient of nonarc variables vector
z is the g x 1 nonarc variable value vector
F is the n x a node-arc incidence matrix of the network, where
Fi,j = -1
if arc j is directed toward node i
Fi,j = 1
if arc j is directed from node i
Fi,j = 0
otherwise
b is the n x 1 node supply/demand vector, where
bi = s
if node i has supply capability of s units of flow
bi = -d
if node i has demand d of units of flow
bi = 0
if node i is a transshipment node
H is the k x a side constraint coefficient matrix for arc variables, where Hi,j is the coefficient of arc j in the ith side constraint
Q is the k x g side constraint coefficient matrix for nonarc variables, where Qi,j is the coefficient of nonarc j in the ith side constraint
r is the k x 1 side constraint right-hand-side vector
l is the a x 1 arc lower flow bound vector
u is the a x 1 arc capacity vector
m is the g x 1 nonarc variable value lower bound vector
v is the g x 1 nonarc variable value upper bound vector