We characterize and demonstrate a solution method for an optimal commodity (sales) tax problem consisting of multiple goods, heterogeneous agents, and a nonconvex policy maker optimization problem. Our approach allows for more dimensions of heterogeneity than has been previously possible, incorporates potential model uncertainty and policy objective uncertainty, and relaxes some of the assumptions in the previous literature that were necessary to generate a convex optimization problem for the policy maker. Our solution technique involves creating a large database of optimal responses by different individuals for different policy parameters and using "Big Data" techniques to compute policy maker objective values over these individuals. We calibrate our model to the United States and test the effects of a differentiated optimal commodity tax versus a flat tax and the effect of exempting a broad class of goods (services) from commodity taxation. We find that only a potentially small amount of tax revenue is lost for a given societal welfare level by departing from an optimal differentiated sales tax schedule to a uniform flat tax and that there is only a small loss in revenue from exempting a class of goods such as services in the United States.
