NUMBERS OF PRIMAL AND DUAL BASES OF NETWORK FLOW AND UNIMODULAR INTEGER PROGRAMS
-
- Ishizeki Takayuki
- The University of Tokyo
-
- Nakayama Hiroki
- The University of Tokyo
-
- Imai Hiroshi
- The University of Tokyo
Search this article
Abstract
To integer programming, algebraic approaches using Grobner 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 Grobner 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.
Journal
-
- Journal of the Operations Research Society of Japan
-
Journal of the Operations Research Society of Japan 48 (3), 183-195, 2005
The Operations Research Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679086399232
-
- NII Article ID
- 110001868874
-
- NII Book ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL BIB ID
- 7456662
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed