  Multilevel techniques are efficient approaches for solving the large linear
systems that arise from discretized partial differential equations and other
problems. While geometric multigrid requires detailed knowledge about the
underlying problem and its discretization, algebraic multigrid aims to be less
intrusive, requiring less knowledge about the origin of the linear system. A
key step in algebraic multigrid is the choice of the coarse/fine partitioning,
aiming to balance the convergence of the iteration with its cost. In work by
MacLachlan and Saad, a constrained combinatorial optimization problem is used
to define the ``best'' coarse grid within the setting of a two-level
reduction-based algebraic multigrid method and is shown to be NP-complete.
Here, we develop a new coarsening algorithm based on simulated annealing to
approximate solutions to this problem, which yields improved results over the
greedy algorithm developed previously. We present numerical results for test
problems on both structured and unstructured meshes, demonstrating the ability
to exploit knowledge about the underlying grid structure if it is available.
