Rule ensembles are designed to provide a useful trade-off between predictive\naccuracy and model interpretability. However, the myopic and random search\ncomponents of current rule ensemble methods can compromise this goal: they\noften need more rules than necessary to reach a certain accuracy level or can\neven outright fail to accurately model a distribution that can actually be\ndescribed well with a few rules. Here, we present a novel approach aiming to\nfit rule ensembles of maximal predictive power for a given ensemble size (and\nthus model comprehensibility). In particular, we present an efficient\nbranch-and-bound algorithm that optimally solves the per-rule objective\nfunction of the popular second-order gradient boosting framework. Our main\ninsight is that the boosting objective can be tightly bounded in linear time of\nthe number of covered data points. Along with an additional novel pruning\ntechnique related to rule redundancy, this leads to a computationally feasible\napproach for boosting optimal rules that, as we demonstrate on a wide range of\ncommon benchmark problems, consistently outperforms the predictive performance\nof boosting greedy rules.\n