Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability

摘要

We discuss matroid-likeness of polyhedra whose facets have non-01-vectors as their normal vectors. We propose, as a generalized class of submodular polyhedra, the class of down-monotone polyhedra whose support functions satisfy submodularity on non-negative vectors. The sets of feasible outflows of certain bipartite generalized networks are examples of such polyhedra. We prove that such polyhedra have certain unbalanced simultaneous exchangeability between two axes. This property gives a simple criterion of optimality for a linear objective function on these polyhedra. We also prove that this simultaneous exchangeability characterizes this generalized class of polyhedra, while a non-simultaneous version of this exchangeability does not.