CPU cache hierarchies are the central solution in bridging the memory wall. A proper understanding of how to trade-off their high cost against performance can lead to cost-savings without sacrificing performance.Due to the combinatorial nature of the problem, there exist a large number of configurations to investigate, making design space exploration slow and cumbersome. To improve this process, this Thesis develops and evaluates a model for optimally trading-off cost and performance of CPU cache hierarchies, named the Optimal Cache Problem (OCP), in the form of a Non-linear Integer Problem. A second goal of this work is the development of an efficient solver for the OCP, which was found to be a branch & bound algorithm and proven to function correctly. Experiments were conducted to empirically analyse and validate the model and to showcase possible use-cases. There, it was possible to ascribe the model outputs on measurable performance metrics. The model succeeded in formalising the inherent trade-off between cost and performance in a way that allows for an efficient and complete search of the configuration space of possible cache hierarchies. In future work, the model needs to be refined and extended to allow for the simultaneous analysis of multiple programs.