TITLE:  Submodular Knapsacks - A Polyhedral Discussion

ABSTRACT:

Submodular and supermodular knapsack sets arise naturally when modeling utilities, risk and probabilistic constraints on discrete variables. Although submodular functions have been explored plentiful with respect to set function optimization, understanding of level sets of these set functions is still underdeveloped. The results with respect to submodular optimization cannot be translated as such when optimizing over the level sets of submodular functions. In particular, even though the convex hull of convex lower envelope of a general submodular function f can be completely characterized, the convex hull description of the lower level set of f is unknown even in the special case when f is monotone. In this talk, we will study the facial structure of the convex hull of the level sets of a given (not necessarily monotone) submodular set function f : {0, 1}^n