Maximizing a Submodular Function by Integer Programming: A Polyhedral Approach

Let N = {1, 2,..., n} be a finite set. A real-valued function f whose domain is all of the subsets of N is said to be submodular if $$f\left( S \right) + f\left( T \right) \geqslant f\left( {S \cup T} \right) + f\left( {S \cap T} \right)for all S,T$$.The problem of maximizing a submodular function includes many NP-hard combinatorial optimization problems, for example the max-cut problem, the uncapacitated facility location problem and some network design problems. Thus, this research is motivated by the opportunity of providing a unified approach to many NP-hard combinatorial optimization problems whose underlying structure is submodular.