  We present a specialized network simplex algorithm for the budget-constrained
minimum cost flow problem, which is an extension of the traditional minimum
cost flow problem by a second kind of costs associated with each edge, whose
total value in a feasible flow is constrained by a given budget B. We present a
fully combinatorial description of the algorithm that is based on a novel
incorporation of two kinds of integral node potentials and three kinds of
reduced costs. We prove optimality criteria and combine two methods that are
commonly used to avoid cycling in traditional network simplex algorithms into
new techniques that are applicable to our problem. With these techniques and
our definition of the reduced costs, we are able to prove a pseudo-polynomial
running time of the overall procedure, which can be further improved by
incorporating Dantzig's pivoting rule. Moreover, we present computational
results that compare our procedure with Gurobi.
