Base polyhedron

Let V be a finite ground set, and let $$b:2^V \to {\mathbb R} \cup \{\infty\}$$ be a submodular function for which b(V) is finite and $$b(\emptyset) = 0$$ . The base polyhedron of b is

$$B(b)=\{x \in {\mathbb R}^V: x(Z) \leq b(Z)\ \forall Z\subseteq V,\ x(V)=b(V)\}.$$

A base polyhedron defined this way is always nonempty. Moreover, if the finite values of b are integer, then B(b) is an integer polyhedron. If b is finite, then the polyhedron is bounded, and it is called a base polytope.

The same definition can be used for a crossing submodular function b. In this case, the polyhedron may be empty, and non-emptiness is characterized by Fujishige's base polyhedron theorem. However if it is non-empty, then there is a submodular function b' for which $$B(b)=B(b')$$ .