A rational design of the underlying architecture of periodic cellular materials can substantially improve the stiffness-to-weight ratio of structural elements. In this study, we exploit this idea to enhance the bending stiffness of a beam. We employ an optimization tool to find the best distribution of relative density through its length and/or across its thickness. The analysis is implemented based on a hybrid-homogenized model that can effectively expedite the analysis process. This model is validated through comparison study with a detailed finite element analysis (FEA) and experimental bending tests on SLA (Stereolithography) 3D printed samples. This model facilitates transforming the general optimization problem into a shape optimization process with relative density of unit cells as design variables. The optimum relative density distribution for maximizing the bending stiffness is obtained by implementing a teaching-learning-based optimization (TLBO) algorithm. The optimization results reveal that the bending stiffness can be substantially increased by grading the relative density through the length and/or across the thickness. The effect of relative density gradient is investigated in details revealing that the optimally graded cellular beams can outperform uniform cellular beams made out of theoretically ideal unit cells by reaching bending stiffness-to-density ratios greater than one. This improvement together with recent advances in additive manufacturing promise the inception of a novel group of high performance lightweight structural elements at a relatively low cost.