Blocking Pairs of Polyhedra Arising from Network Flows
CORNELL UNIV ITHACA NY DEPT OF OPERATIONS RESEARCH
Pagination or Media Count:
A study is made of blocking pairs of polyhedra blocking pairs of matrices that arise in or can be transformed into a network flow context. For example, the blocking polyhedron of the polyhedron generated by all integral feasible flows in a capacity-constrained supply-demand network where all the data are integral is explicitly determined, and a simple algorithm is described for solving the associated integral packing problem. Applications of these results to k-ways in directed graphs, 0,1-matrices with prescribed row and column sums, and to flow arborescences are described.
- Operations Research