A major Dutch bank asked us to help them with assigning customers to email campaigns to achieve the maximal ROI. This is a classical optimization problem which can be solved using linear programming. However, the size of the data was such that linear solvers they were trying to use were either running out of memory, or taking a very long time to compute the solutions.
We proposed using a greedy algorithm (W) that finds a solution close to the optimal in a much shorter time: minutes, rather than days. We delivered the algorithm in a form of a compact C program that could be easily integrated with the bank’s infrastructure.