  We consider the problem of maximizing a non-negative submodular set function
$f:2^N \rightarrow \mathbb{R}_+$ over a ground set $N$ subject to a variety of
packing type constraints including (multiple) matroid constraints, knapsack
constraints, and their intersections. In this paper we develop a general
framework that allows us to derive a number of new results, in particular when
$f$ may be a non-monotone function. Our algorithms are based on (approximately)
maximizing the multilinear extension $F$ of $f$ over a polytope $P$ that
represents the constraints, and then effectively rounding the fractional
solution. Although this approach has been used quite successfully, it has been
limited in some important ways. We overcome these limitations as follows.
  First, we give constant factor approximation algorithms to maximize $F$ over
a down-closed polytope $P$ described by an efficient separation oracle.
Previously this was known only for monotone functions. For non-monotone
functions, a constant factor was known only when the polytope was either the
intersection of a fixed number of knapsack constraints or a matroid polytope.
Second, we show that contention resolution schemes are an effective way to
round a fractional solution, even when $f$ is non-monotone. In particular,
contention resolution schemes for different polytopes can be combined to handle
the intersection of different constraints. Via LP duality we show that a
contention resolution scheme for a constraint is related to the correlation gap
of weighted rank functions of the constraint. This leads to an optimal
contention resolution scheme for the matroid polytope.
  Our results provide a broadly applicable framework for maximizing linear and
submodular functions subject to independence constraints. We give several
illustrative examples. Contention resolution schemes may find other
applications.
