Heating, ventilation, and air-conditioning costs dominate the overall energy bill of commercial buildings. These costs are even higher in developing countries where diesel generators provide backup power during recurrent power outages. In this work, we propose two efficient approaches to minimize energy costs associated with HVAC systems in the presence of outages and a mix of supply resources including grid, DG, solar and batteries. First, we develop an MILP optimization framework to solve the problem optimally. The framework uses novel relaxed HVAC models that speed-up computation without compromising solution accuracy. Thereafter, we develop a fast heuristic algorithm which uses a derived closed form solution for the optimal pre-cooling time and provides near optimal solutions in about three orders of magnitude less time compared to the optimization framework. Our experimental results demonstrate that both approaches yield average savings of 20% relative to the baseline operational practices in office buildings and cell towers.