In recent years, local message-passing algorithms (i.e., belief propagation, max-product) have been widely used to compute approximate solutions in graphs with cycles. We describe a class of reweighted message-passing algorithms, and demonstrate how they can be understood as methods for solving graph-structured optimization problems. These modified algorithms have advantages over standard methods, including unique fixed points and guaranteed upper bounds (reweighted belief propagation), and performance guarantees (reweighted mix-product). We discuss applications of graphical models and message-passing to statistical image processing and error-control coding, as well as directions for future research.