Value-directed Compression of Large-scale Assignment Problems

Data-driven analytics—in areas ranging from consumer mar-keting to public policy—often allow behavior prediction at the level of individuals rather than population segments, of-fering the opportunity to improve decisions that impact large populations. Modeling such (generalized) assignment prob-lems as linear programs, we propose a general value-directed compression technique for solving such problems at scale. We dynamically segment the population into cells using a form of column generation, constructing groups of individ-uals who can provably be treated identically in the optimal solution. This compression allows problems, unsolvable us-ing standard LP techniques, to be solved effectively. Indeed, once a compressed LP is constructed, problems can solved in milliseconds. We provide a theoretical analysis of the meth-ods, outline the distributed implementation of the requisite data processing, and show how a single compressed LP can be used to solve multiple variants of the original LP near-optimally in real-time (e.g., to support scenario analysis). We also show how the method can be leveraged in integer pro-gramming models. Experimental results on marketing con-tact optimization and political legislature problems validate the performance of our technique