Difference between submodular polyhedron and base polyhedron Can anyone tell me the difference between base polyhedron and submodular polyhedron of a submodular function $f$ defined over base set $V$ ?.
According to the definition, the base polyhedron is same as submodular polyhedron.
Base polyhedron definition says, $ \forall A \subseteq V, s(A) \leq f(A)$ and $s(V) = f(V)$, whereas submodular polyhedron definition says, $\forall A \subseteq V, s(A) \leq f(A)$. Here $s(A) = \sum_{k \in A} s_k$
since the definition is based on subset, submodular polyhedron should automatically contain $s(V) = f(V)$ 
 A: This is pretty old but I might as well:
The equality constraint must hold for all points in the base polyhedron.
For the submodular polyhedron you only have $  s(V) \leq f(V)$, so you are allowed $s(V) < f(V)$ which is not the case for the base polyhedron since it must have equality for $V$.
Intuitively, in a certain sense you can view the base polyhedron as describing just the "outer shell" of the submodular polyhedron. In the language of matroids, if we restrict $s$ to be nonnegative, the submodular polyhedron is the convex hull of independent sets of a matroid, while the base polyhedron is the convex hull of the bases of a matroid.
Furthermore, there are certain things you can do with the base polyhedron that you cannot do with the submodular one. For example, you may define the Lovasz Extension as the optimal solution of an LP in the base polyhedron, given an input cost vector in $\mathbb{R}^n$. If the LP is taken in the submodular polyhedron instead, the costs have to be nonnegative. So in some sense, the base polyhedron allows a more general definition of the Lovasz extension.
Base polyhedra are also known as
"generalized permutahedra" and are known to have certain nice properties: every edge of a base polyhedron is parallel to $\mathbf{e}_i-\mathbf{e}_j$ for some $i,j$ where $\mathbf{e}_i$ is the i-th standard basis vector.
