Routing, subchannel scheduling, and power allocation are generally treated as separate problems in relay-enhanced OFDMA-based cellular networks. They are mostly modeled using non-linear constraints to maximize either sum rate or minimum rate. Although separation of problems simplifies modeling, it can lead to suboptimal solutions which can degrades network efficiency (i.e., low sum rate or low minimum rate). Also, models that include non-linear constraints generally belong to the NP-hard class. In this study, we jointly optimize routing, subchannel scheduling, and power allocation in relay-enhanced OFDMA-based cellular networks through a novel Linear Programming (LP) framework employing discrete power levels. Our framework is comprised of LP models for the following problems: Sum Rate Maximization (SRM), Max-Min Fairness (MMF), and Joint Sum Rate Maximization and Max-Min Fairness (JSRM(3)F). We investigate the trade-offs in sum rate maximization and maxmin fairness in terms of achievable maximum data rates and subchannel sharing by numerical evaluations of the LP models. We show that maximum data rates obtained with discrete power allocation are near-optimal even with a few discrete power levels. We provide upper bounds for joint maximization of sum rate and minimum rate. Furthermore, the results of this study reveal that fairness has a significant impact on subchannel sharing.