Overdiagnosis of breast cancer, defined as diagnosing a cancer that would otherwise not cause symptoms or death in a patient's lifetime, costs U.S. health care system over $1.2 billion annually. Overdiagnosis rates, estimated to be around 10%-40%, may be reduced if indolent breast findings can be identified and followed with noninvasive imaging rather than biopsy. However, there are no validated guidelines for radiologists to decide when to choose imaging options recognizing cancer grades and types. The aim of this study is to optimize breast cancer diagnostic decisions based on cancer types using a large-scale finite-horizon Markov decision process (MDP) model with 4.6 million states to help reduce overdiagnosis. We prove the optimality of a divide-and-search algorithm that relies on tight upper bounds on the optimal decision thresholds to find an exact optimal solution. We project the high-dimensional MDP onto two lower dimensional MDPs and obtain feasible upper bounds on the optimal decision thresholds. We use real data from two private mammography databases and demonstrate our model performance through a previously validated simulation model that has been used by the policy makers to set the national screening guidelines in the United States. We find that a decision-analytical framework optimizing diagnostic decisions while accounting for breast cancer types has a strong potential to improve the quality of life and alleviate the immense costs of overdiagnosis. Our model leads to a reduction in overdiagnosis on the screening population, which translates into an annual savings of approximately $300 million for the U.S. health care system.