The authors discuss the problem of hedging between the natural gas and electric power markets. Based on multiple forecasts for natural gas prices, natural gas demand, and electricity prices, a stochastic optimization model advises a decision maker on when to buy or sell natural gas and when to transform gas into electricity. For relatively small models, branch-and-bound solves the problem to optimality. Larger models are solved using Benders decomposition and Lagrangian relaxation. They apply their approach to the system of an electric utility and succeed in solving problems with 50000 binary variables in less than 4 min to within 1.16% of the optimal value.