This paper describes an optimization algorithm that provides an economical Vertical Navigation profile plan by finding the combinations of climb, cruise and descent speeds, as well as the altitudes for an aircraft to minimize flight costs. The computational algorithm profits from a space search reduction algorithm to reduce the initial number of speed and altitude combinations.Additional search space reductions were performed with the implementation of the branch and cut algorithm. A bounding function that correctly estimates the flight cost considering step climbs was developed to reduce the number of calculations. The full flight fuel burn cost was obtained using a performance database- based method. The fuel flight cost was computed using the cost index.This algorithm used a performance database instead of equations of motion to compute fuel burn. This database was developed and validated by our industrial partner using real flight experimental data.To validate the algorithm, its results were compared against three different algorithms: an “exhaustive search algorithm”, “Branch and Cut” and “Search Space Reduction Algorithm”. The solution provided by the algorithm was also compared to the solution provided by the commercial flight management system used for this study. These comparisons proved that the developed algorithm systematically found the optimal solution, and these solutions were often significantly better than those provided by a commercial flight management system.