Cost-effectiveness analysis is widely used by policymakers to prioritize interventions that improve a population’s health. Net monetary benefit (NMB) is a metric used for the comparison of medical care strategies, which converts an intervention’s health-benefits to monetary value using the willingness to pay (WTP) as the exchange rate. There is no universally accepted value for WTP, and its value affects the optimal choice of strategies. In this paper, we propose constructing a comprehensive menu of cost-effective strategies for the policymaker to choose from and develop a novel algorithm that efficiently generates the cost-effectiveness frontier. The algorithm is based on successive application of the incremental cost-effectiveness ratio (ICER) minimization problem. We apply our modelling framework to design cost-effective hearing loss screening strategies for patients with cystic fibrosis (CF) disease. We build a stochastic optimization problem based on a hidden Markov reward model to optimally decide the timing and modality of audiometry. We solve the associated NMB and ICER optimization problems using a partially observable Markov decision process (POMDP) and a constrained, non-linear POMDP model, respectively. We build a data-driven model using evidence from the literature and use a grid-based approximation method to solve the problem numerically. We develop multiple heuristic and approximate policies and evaluate their performance against the optimal policy based on several metrics using a simulation model. The policymaker can use the simulation results to decide the trade-off between performance and ease of implementation of the various policies. We prove several theoretical properties of the proposed solution methods.