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

AbstractIt 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 RV 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 P⊆RV, 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 RV.This reveals the geometric structure of polybasic polyhedra and its relation to submodularity