Even though rail transportation is one of the most fuel efficient forms of surface transportation, the cost of fuel constitutes one of the major categories of very high operating costs for railroad companies. In the United States, unlike in Europe, fueling cost is, by far, the highest single operating cost. For larger companies with several thousands of miles of rail network, the fuel bills often run into several billions of dollars annually. The railroad fueling problem considered in this paper has three distinct cost components. Fueling stations charge a location-dependent price for the fuel in addition to a fixed contracting fee over the entire planning horizon. In addition, the railroad company must also bear incidental and notional costs for each fueling stop. This paper proposes a mixed-integer linear program model that determines the optimal strategy for contracting and fuel purchase schedule decisions that minimize overall costs under certain reasonable assumptions. The model is tested on large, real-life problem situations. The mathematical model is further refined by introduction of several feasible mixed-integer program (MIP) cuts. The paper compares the efficiency of different MIP cuts to reduce the run time. Although the scale of the problem was expected to diminish the model performance, run time and memory requirements were observed to be fairly reasonable. It, thus, establishes that exact workable methods should be considered for actual implementation of this problem at railroad companies, in addition to heuristic approaches. This paper has given us a reasonable satisfaction that we have successfully demonstrated the capability to solve a dynamic version of the locomotive refueling problem where the capacity of the fueling yards vary across days during the planning horizon.