Optimizing list selection

[jdb7s]

Issue:

For our direct mail acquisition program we pay to rent lists from a bunch of organizations for one-time use. The cost per list varies but for the purpose of this problem let’s say that each list costs $70 per thousand names (we will refer to that as the “actual list cost”). Because we are getting names from a bunch of different places there is a fair amount of overlap. For example, we may find that 25% of the names on the X list overlap with the names on the Y list, and so on. So our effective cost per name then becomes much higher, like $120 per thousand names since we are paying for a lot of names multiple times (let’s call this the “effective list cost”).

Available data:

We now have files from past mailings that contains a master list of every name that we rented and shows all the lists that a name appeared on.  So if John X was on 10 lists we can see each of those 10 lists. If Mary Y appeared on 30 lists we can see all 30.

Goal:

Optimize acquisition list selects so that we can lower the effective list cost by reducing the number of list sources.  For example could we reduce the number of lists by say 20%, but only reducing the audience size by 5% through not renting lists x1, x2, x3, and x4 because they have the highest degree of overlap?

Question:

I was hoping to get some ideas on which sas procedures/approaches could best answer the question

[RobPratt · Accepted solution]

If you want to find a minimum number of lists to cover all the names, that is the set cover problem.  If the lists have different prices and you want to minimize the total cost, that is the weighted set cover problem, mentioned on the same page.  If you want to maximize the number of names covered subject to a budget on the number or total cost of the lists, that is the maximum coverage problem, also known as the partial set cover problem.

You can solve all of these variants by calling the MILP solver in PROC OPTMODEL.  You would declare a binary decision variable for each list and a constraint for each name.  For the partial set cover problem, you would declare an additional binary decision variable for each name to indicate whether it is covered.