We present a unified framework for designing polynomial time approximation schemes (PTASs) for `dense'' instances of many $\NP$-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum $k$-way cut with and without specified sources, and maximum 3-satisfiability. Dense graphs for us are graphs with minimum degree $\Theta(n)$, although some of our algorithms work so long as the graph is dense `on average''. (Denseness for non-graph problems is defined similarly.) The unified framework begins with the idea of {\em exhaustive sampling:} picking a small random set of vertices, guessing where they go on the optimum solution, and then using their placement to determine the placement of everything else. The approach then develops into a PTAS for approximating certain {\em smooth\/} integer programs where the objective function is a `dense'' polynomial of constant degree.