Looked again, the problem is least cost network flows. That is a linear programming problem. In that problem, if the arc capacities are integers, and in this practical problem they are, then the simplex algorithm can easily start with a basic, feasible, integer solution, and the simplex iterations will automatically maintain an integer solution and, then, find an optimal integer solution which provides the optimal assignments.

When we apply the simplex algorithm to least cost network flows, we get to take advantage of the fact that the problem is not fully general linear programming, and the advantage we can take is huge. E.g., the arcs of a basic, feasible solution form just a spanning tree in the network; the 'entering variable' in the simplex algorithm just adds an arc to the spanning tree and, thus, yields a circuit; we run flow around the circuit in the direction that makes money until the flow on some arc is zero and that arc determines the 'leaving variable'. Using the 'strongly feasible' basis ideas of W. Cunningham, long at Waterloo, we can avoid cycling.

But, the simplex algorithm for least cost network flows, as far as I know, is not guaranteed, worst case polynomial.

However, read:

Dimitri P. Bertsekas, 'Linear Network Optimization: Algorithms and Codes', ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.

and in there, or elsewhere in Bertsekas's work, is an algorithm for least cost network flows and that is worst case polynomial.

Done.

And I covered nothing classified!

And for this thread, we have a "how to" with high precision from some applied math.