We present a new family of strategies that decompose large optimization problems by exploiting their underlying graph structure. A distinctive feature of these strategies is that the use overlapping partitions to promote convergence. We also present a new family of preconditioning strategies for large structured linear algebra systems arising in optimization. These techniques use ADMM as a preconditioner and we show that they induce a favorable eigenvalue spectrum and can overcome scalability limitations of Schur complement decomposition. We illustrate the benefits of these approaches in applications arising in network control and estimation, optimal control, and stochastic programming.