Characterizing and recognizing generalized polymatroids (Q403645)

A generalized polymatroid is a polyhedron given by supermodular and submodular functions p and b, both mapping the empty set to zero and satisfying a ``cross-inequality''. Generalized polymatroids generalize polymatroid, contra-polymatroids, base-polyhedra, and submodular polyhedra. This paper focuses on characterizations and recognition complexity of generalized polymatroids. The main results are the following: A polyhedron is a generalized polymatroid if it can be defined by set functions p,b such that for every primal objective with finite value some optimal solution is ``laminar'', where the latter is a combinatorial property of the support of the solution. While it is shown that verifying the above characterization is NP-hard, the authors give a polynomial-time algorithm that given a system of linear inequalities checks if a polyhedron is a generalized polymatroid. Another result is that the known property of integral generalized polymatroids that their intersection is integral in fact characterizes them in the following sense: If the intersection of a polyhedron P with every integral generalized polymatroid is integral, then P is a generalized polymatroid. Finally, bounded generalized polymatroids are characterized as satisfying certain Minkowski sum equations related to generalized permutahedra.