Maximizing a supermodular function is like minimizing a submodular function. This is a polynomial time activity, for which several algorithms are known (search google for **min norm algorithm** and you'll find many hits, including to a paper by Fujishige).

There are several other approaches available for solving submodular minimization. Do not confuse it with submodular maximization (or supermodular minimization), for which there are greedy algorithms --- because these problems are NP-Hard to approximate to a factor better than $1-1/e$ unless more structure is assumed. Again, google will find you many hits on the greedy algorithm for submodular maximization.