The New York State Department of Taxation and Finance (NYS DTF) collects over $1 billion annually in assessed delinquent taxes. The mission of DTF's Collections and Civil Enforcement Division (CCED) is to increase collections, but to do so in a manner that respects the rights of citizens, by taking actions commensurate with each debtor's situation. CCED must accomplish this in an environment with limited resources. In a collaborative work, NYS DTF, IBM Research, and IBM Global Business Services developed a novel tax collection optimization solution to address this challenge. The operations research-based solution combines data analytics and optimization using the unifying framework of constrained Markov decision processes (C-MDP). The system optimizes the collection actions of agents with respect to maximizing long-term returns, while taking into account the complex dependencies among business needs, resources, and legal constraints. It generates a customized collections policy instead of broad-brush rules, thereby improving both the efficiency and adaptiveness of the collections process. It also enhances and improves the tax agency's ability to administer taxes equitably across the broad scope of individual taxpayers' situations. The system became operational in December 2009; from 2009 to 2010, New York State increased its collections from delinquent revenue by $83 million (8 percent) using the same set of resources. Given a typical annual increase of 2 to 4 percent, the system's expected benefit is approximately $120 to $150 million over a period of three years, far exceeding the initial target of $90 million. © 2012 INFORMS.