This paper presents models and optimization algorithms to compute the fuel-optimal energy management strategies for a parallel hybrid electric powertrain on a given driving cycle. Specifically, we first identify a mixed-integer model of the system, including the engine on/off signal and the gear-shift commands. Thereafter, by carefully relaxing the fuel-optimal control problem to a linear program, we devise an iterative algorithm to rapidly compute the minimum-fuel energy management strategies including the optimal gear-shift trajectory. We validate our approach by comparing its solution with the globally optimal one obtained solving the mixed-integer linear program and with the one resulting from the implementation of the optimal strategies in a high-fidelity nonlinear simulator.We showcase the effectiveness of the presented algorithm by assessing the impact of different powertrain configurations and electric motor size on the achievable fuel consumption.Our numerical results show that the proposed algorithm can assess fuel-optimal control strategies with low computational burden, and that powertrain design choices significantly affect the achievable fuel consumption of the vehicle.