Some mining operations eventually transition underground because surface mining becomes increasingly expensive as one progresses downward. Mining firms often delay this transition because large underground infrastructure costs are incurred up front, whereas underground extraction may occur over decades. When and how deep to install the underground infrastructure, as well as extraction schedules above and below ground, are decisions with a sizable impact on profits. This article addresses these questions while considering realistic factors, including choices of cutoff grades (minimum ore concentration at which the extracted material is processed to recover ore) and mining rates. We present a large longest-path representation of the problem and show that it can be solved via a series of small longest-path problems. The latter representation is not a decomposition of the original network but takes advantage of the structure of the problem. Together, the small networks require only a few seconds to solve. We illustrate our approach using data from a South African mine and provide insights regarding the effects of ore prices, discount rates, and their interactions on the characteristics of optimal solutions; we find that common wisdom is not always applicable. Our solutions have significantly higher profits than benchmark solutions, representing up to billions of dollars.