Numbers of primal and dual bases of network flow and unmodular integer programs

In integer programming, algebraic approaches using Gröbner bases and standard pairs via toric ideals have been studied in recent years. In this paper, we consider a unimodular case, e.g., network flow problems, which enables us to analyze primal and dual problems in an equal setting. By combining existing results in an algebraic approach, we prove a theorem that the maximum number of dual feasible bases is obtained by computing the normalized volume of the convex hull generated from column vectors of a coefficient matrix in the primal standard form. We apply the theorem, partly with Gröbner bases theory, to transportation problems and minimum cost flow problems on acyclic tournament graphs. In consequence, we show new algebraic proofs to the Balinski and Russakoff's result on the dual transportation polytope and Klee and Witzgall's result on the primal transportation polytope. SImilarly results for the primal case of acyclic tournament graphs are obtained by using Gelfand, Graev and Postnikov's result for nilpotent hypergeometric functions. We also give a bound of the number of feasible bases for its dual case.