Computer-Implemented Marketing Optimization Systems And Methods

• US 20100049535A1
• Filed: 08/20/2008
• Published: 02/25/2010
• Est. Priority Date: 08/20/2008
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Liao, Yi, Chari, Manoj Keshavmurthi, Opp, Michelle Gail, Gopalakrishnan, Balaji
• Granted Patent: US 8,296,182 B2
• Time in Patent Office: Days
• US Class Current: 705/1.100
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0244 Optimization

Abstract

Computer-implemented systems and methods are provided for determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints. A plurality of offer sets is generated for each customer. An approximate highest reduced adjusted objective for each of the offer sets for each customer is calculated, and the customers are bucketed based on the highest adjusted objective value associated with each customer. The buckets are collapsed into a single bucket record containing a plurality of aggregate offer set columns, and an aggregate offer set column is selected from each bucket record for each bucket. Each bucket associated with a selected offer set is disaggregated, and the action item included in the selected offer set is stored in a computer-readable memory.

Claims

1. A computer-implemented method of determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said method comprising:

combining the plurality of aggregate constraints with the global set of action items such that records associated with each member of the global set of action items identify the aggregate constraints with which that member of the global set of action items is associated in a bit-wise fashion in order to create a measures data structure;

generating a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set based on objective coefficients calculated in memory utilizing the measures data structure, and the plurality of individual constraints;

selecting an offer set for each customer from the plurality of generated offer sets for that customer such that the objective function is maximized; and

storing the action item included in the selected offer set in a computer-readable memory.

2. The method of claim 1, wherein the aggregate constraints identify limits on action items over the plurality of customers;

wherein aggregation of offer sets in the generating step requires a recalculation of the aggregate constraints;

wherein the measures data structure is used to recalculate the aggregate constraints in memory without requiring storage of the recalculated aggregate constraints in non-volatile memory.

3. The method of claim 1, wherein the measures data structure accounts for at least three aggregate constraints;

wherein a first bit in the measures data structure identifies whether a first aggregate constraint is associated with each member of the global set of action items;

wherein a second bit in the measures data structure identifies whether a second aggregate constraint is associated with each member of the global set of action items;

wherein a third bit in the measures data structure identifies whether a third aggregate constraint is associated with each member of the global set of action items.

4. The method of claim 1, wherein the measures data structure includes an offer field identifying an action item from the global set of action items, the measures data structure also including an indicator field identifying the aggregate constraints with which the action item is associated.

5. A computer-implemented system for performing an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said system comprising:

a measures data structure generator configured to combine the plurality of aggregate constraints with the global set of action items such that records associated with each member of the global set of action items identify the aggregate constraints with which that member of the global set of action items is associated in a bit-wise fashion to generate a measures data structure;

an offer set generator configured to generate a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set based on objective coefficients calculated in memory utilizing the measures data structure, and the plurality of individual constraints;

an offer set selector configured to select an offer set for each customer from the plurality of generated offers sets for that customer such that the objective function is maximized; and

a memory for storing the selected offer set.

6. A computer-implemented method of generating a plurality of offer sets for each of a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said method comprising:

generating a first plurality of offer sets for each customer that include an action item from a global set of action items in each offer set based on an objective function;

applying a Lagrange relaxation technique to the objective function based on the plurality of aggregate constraints to generate a relaxed objective function;

applying a subgradient algorithm to the relaxed objective function based on the first plurality of offer sets to calculate a first upper bound objective value;

generating a second plurality of offer sets based upon an adjusted objective function;

reapplying a subgradient algorithm to the relaxed objective function based on the second plurality of offer sets to calculate a second upper bound objective value;

comparing the second upper bound objective value to the first upper bound objective value;

appending the second plurality of offer sets to the first plurality of offer sets; and

storing the first plurality of offer sets in a computer-readable memory;

wherein the steps of generating a second plurality of offer sets, reapplying a subgradient algorithm, and appending the second plurality of offer sets are repeated if the difference between the second upper bound objective value and the first upper bound objective value is greater than a threshold value.

7. The method of claim 6, wherein the plurality of customers form a subset of a customer pool;

wherein a member of the customer pool having identical individual constraints as a member of the plurality of customers is associated with identical offer sets as the member of the plurality of customers.

8. The method of claim 6, wherein the Lagrange relaxation technique is a linear programming relaxation.

9. The method of claim 7, wherein the Lagrange relaxation technique utilizes an OCTANE heuristic.

10. A computer-implemented system of generating a plurality of offer sets for each of a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said system comprising:

a candidate calculator configured to generate a first plurality of offer sets for each customer, the offers sets including an action item from a global set of action items in each offer set based on an objective function;

a subgradient calculator configured to make a determination as to the sufficiency of the first plurality of offer sets, the subgradient calculator comprising;

a constraint integrator configured to apply a Lagrange relaxation technique to the objective function based on the plurality of aggregate constraints to generate a relaxed objective function;

a subgradient algorithm calculator configured to apply a subgradient algorithm to the relaxed objective function based on the first plurality of offer sets to calculate a first upper bound objective value;

wherein the candidate calculator and the subgradient calculator are further configured to generate a second plurality of offer sets and a second upper bound objective value;

wherein the second plurality of offer sets is appended to the first plurality of offer sets to generate a compendium of offer sets;

a memory for storing the compendium of offer sets;

a comparison calculator configured to direct the candidate calculator and the subgradient calculator to operate on a third plurality of offer sets if a difference between the first upper bound objective value and the second upper bound objective value is not within a threshold value.

11. A computer-implemented method of determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said method comprising:

generating a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set;

calculating an approximate highest adjusted objective value for each of the generated offer sets for each customer;

bucketing the customers based on the highest adjusted objective value associated with each customer;

collapsing each bucket into a single bucket record containing a plurality of aggregate offer set columns;

selecting an aggregate offer set column from each bucket record;

disaggregating each bucket to associate a selected offer set with each customer in the bucket according to the selected aggregate offer set column for the bucket; and

storing the action item included in the selected offer set in a computer-readable memory.

12. The method of claim 11, wherein the bucketing step further comprises:

grouping the customers according by offer set having the highest adjusted objective value for each customer;

sorting each group of customers by the highest adjusted objective value for the offer set associated with the group; and

aggregating customers within each group into buckets containing up to a threshold number of customers.

13. The method of claim 11, wherein each aggregate offer set column represents one or more offer sets;

wherein each offer set in the aggregate offer set column is associated with at least one customer.

14. The method of claim 13, wherein the aggregate offer set for each bucket is selected using an integer programming heuristic.

15. The method of claim 11, further comprising the step of selecting an offer set for a subset of the plurality of customers that offers a maximum objective return, is associated with a target constraint, and does not violate any constraints.

16. The method of claim 15, wherein the offer sets are selected by using a gradient constraint fixing heuristic.

17. The method of claim 16, wherein the gradient constraint fixing heuristic configured to:

select an aggregate constraint that represent agent constraints;

select a subset of the plurality of offer sets that are associated with the agent constraint such that the agent constraint is saturated;

wherein customers associated with the subset of the plurality of offer sets and the agent constraints are excluded from consideration in the calculating, bucketing, collapsing, selecting, and disaggregating steps.

18. The method of claim 17, wherein agent constraints are identified by computing an average gradient value for each aggregate constraint;

wherein aggregate constraints that have only positive coefficients and a positive right hand side limit are deemed agent constraints.

19. The method of claim 18, wherein the agent constraint identifies the number of customers a personal banking representative is permitted to contact by phone.

20. A computer-implemented system for determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said system comprising:

a candidate calculator configured to generate a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set;

a highest adjusted objective value calculator configured to calculate an approximate highest adjusted objective value for each of the generated offer sets for each customer;

a customer bucket calculator configured to group the customers based on the highest adjusted objective value associated with each customer;

a customer bucket aggregator configured to collapse each bucket into a single bucket record containing a plurality of aggregate offer set columns;

a bucket solver configured to select an aggregate offer set column for each bucket record;

a customer bucket disaggregator configured to disaggregate each bucket to associate a selected offer set with each customer in the bucket according to the selected aggregate offer set column for the bucket; and

a memory for storing the action item included in the selected offer set for each customer.

21. A computer-implemented method of determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said method comprising:

generating a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set;

calculating a highest adjusted objective value for each of the generated offer sets for each customer;

bucketing the customers based on the highest reduced adjusted objective associated with each customer;

collapsing each bucket into a single bucket record containing a plurality of aggregate offer set columns;

selecting an aggregate offer set column for each bucket;

disaggregating each bucket to associate a selected offer set with each customer in the bucket according to the selected aggregate offer set column for the bucket;

retaining a portion of the customer-selected offer set associations as final customer-selected offer sets;

repeating the steps of bucketing the customers, collapsing each bucket, selecting an aggregate offer set, disaggregating each bucket, and retaining a portion of the customer-selected offer set associations utilizing a smaller bucket size; and

storing the action item included in the final customer-selected offer set in a computer readable memory.

22. The method of claim 21, wherein the repeating step is executed a user-defined number of times.

23. The method of claim 21, wherein the bucketing the customers, collapsing each bucket, selecting an aggregate offer set, disaggregating each bucket, and retaining a portion of the customer-selected offer set associations utilizing a smaller bucket size are repeated for a reduced set of customers, the reduced set of customers not including customers associated with final customer-selected offer sets.

24. A computer-implemented system for determining an action item from a global set of action items for a plurality of customers based on an objective function, a plurality of individual constraints, and a plurality of aggregate constraints, said system comprising:

a candidate calculator configured to generate a plurality of offer sets for each customer that include an action item from the global set of action items in each offer set;

a highest adjusted objective value calculator configured to calculate an approximate highest adjusted objective value for each of the generated offer sets for each customer;

a customer bucket calculator configured to group the customers based on the highest adjusted objective value associated with each customer;

a customer bucket aggregator configured to collapse each bucket into a single bucket record containing a plurality of aggregate offer set columns;

a bucket solver configured to select an aggregate offer set column for each bucket record;

a customer bucket disaggregator configured to disaggregate each bucket to associate a selected offer set with each customer in the bucket according to the selected aggregate offer set column for the bucket; and

an offer set evaluator configured to retain a number of selected offer sets based on a criteria, the offer set evaluator configured to discard the remainder of the selected offer sets;

a memory for storing the action item included in the retained selected offer sets;

wherein the computer-implemented system is configured to operate the customer bucket calculator, the customer bucket aggregator, the bucket solver, the bucket disaggregator, and the offer set evaluator over a pre-specified number of loops;

wherein for each loop, a bucket group size of the customer calculator is reduced;

wherein customers associated with a retained selected offer set are not considered in subsequent loops;

wherein all selected offer sets are retained during a final traversal of the loop.