Interference and collisions greatly limit the throughput of mesh networks that used contention-based MAC protocols such as 802.11. It is widely believed that significantly higher throughput is achievable if transmissions are scheduled. However, since the typical approach to this throughput optimization requires optimizing over a space that is exponential in the number of links, the optimal throughput has appeared to be computationally intractable for all but small networks. This research presents techniques that are typically able to efficiently compute optimal schedules.<br/><br/>The technique consists of two layers of optimization. The inner optimization computes an estimate of the throughput. This optimization is a standard linear or nonlinear constrained optimization, depending on the objective function. The outer iteration uses the Lagrange multipliers from the inner optimization to modify the space over which inner optimization is performed. This is a graph theoretic optimization known as the maximum weighted independent set (MWIS) problem. The solvability of this problem is extensively studied, and the empirical evidence shows that usually MWIS arising from wireless mesh network can be solved quickly.<br/><br/>Together, these techniques allow optimal schedules to be computed for networks with hundreds and even a few thousand links. Thus, the approach is practical for the current and planned urban mesh networks. The techniques have been verified on networks generated with a realistic urban propagation simulator. In this setting, it is shown that optimal scheduling increases the throughput by a factor between three and ten over 802.11 CSMA/CA, depending on the density of the mesh routers and gateways.