Connected Vehicle (CV) technology, which allows traffic information sharing, and Hybrid Electrical Vehicles (HEV) can be combined to improve vehicle fuel efficiency. However, transient traffic information in CV environment necessitates a fast HEV powertrain optimization for real-time implementation. Model Predictive Control (MPC) with Linearization is proposed, but the computational effort is still prohibitive. The Equivalent Consumption Minimization Strategy (ECMS) and Adaptive-ECMS are proposed to minimize computation time, but unable to guarantee charge-sustaining-operation (CS). Fast analytical result from Pontryagin's Minimum Principles (PMP) is possible but the input has to be unconstrained. Numerical solutions with Linear Programming (LP) are proposed, but over-simplifications of the cost and constraint functions limit the performance of such methods. In this paper, a nonlinear CS constraint is transformed into linear form with input variable change. With linear input and CS constraints, the problem is solved with Separable Programming by approximating the nonlinear cost with accurate linear piecewise functions which are convex. The piecewise-linear functions introduce new dimensionless variables which are solved as a large-dimension constrained linear problem with efficient LP solvers. Comparable fuel economy with Dynamic Programming (DP) is shown, with maximum fuel savings of 7% and 21.4% over PMP and Rule-Based (RB) optimizations. Simulations with different levels of vehicle speed prediction uncertainties to emulate CV settings are presented.