In Case-Based Reasoning (CBR), new problems are solved by retrieving similar previously solved cases and adapting their solutions. The new case is then stored appropriately in the case-base for future use. It is a fundamental problem to control the growth of case-base and the case-base maintenance step retains cases in the case-base based on an estimate of their usefulness in solving new problems. We propose an optimization formulation to identify an optimal set of representative cases called the optimal footprint of the case-base. The optimization formulation ensures that the optimal footprint set strikes a right trade-off between minimizing the number of cases and maximizing their ability to solve the remaining cases in the case-base. This trade-off is studied empirically in this paper. We also illustrate the trade-off between the size and performance of optimal footprint in the context of regression. Copyright © 2018, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.