Polybasic polyhedra: structure of polyhedra with edge vectors of support size at most 2

It has widely been recognized that submodular set functions and base polyhedra associated with them play fundamental and important roles in combinatorial optimization problems. In the present paper, we introduce a generalized concept of base polyhedron. We consider a class of pointed convex polyhedra in R^V whose edge vectors have supports of size at most 2. We call such a convex polyhedron a polybasic polyhedron. The class of polybasic polyhedra includes ordinary base polyhedra, submodular/supermodular polyhedra, generalized polymatroids, bisubmodular polyhedra, polybasic zonotopes, boundary polyhedra of flows in generalized networks, etc. We show that for a pointed polyhedron PR^V, the following three statements are equivalent:

(1) P is a polybasic polyhedron.

(2) Each face of P with a normal vector of the full support V is obtained from a base polyhedron by a reflection and scalings along axes.

(3) The support function of P is a submodular function on each orthant of R^V.

This reveals the geometric structure of polybasic polyhedra and its relation to submodularity.