Method for optimizing net present value of a cross-selling marketing campaign

• US 6,993,493 B1
• Filed: 08/05/2000
• Issued: 01/31/2006
• Est. Priority Date: 08/06/1999
• Status: Expired due to Term

• Current Assignee: Experian Information Solutions Incorporated (Experian plc)
• Original Assignee: Marketswitch Corp. (Experian plc)
• Inventors: Fishman, Vladimir, Gibiansky, Leonid, Galperin, Yuri
• Primary Examiner(s): MEINECKE DIAZ, SUSANNA M
• Application Number:
  US09/634,624
• Time in Patent Office: 2,005 Days
• Field of Search: 705/10, 705/1, 705/14, 705/35, 705/36, 703/2, 703/6, 706/925
• US Class Current: 705/7.29
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06375 Prediction of business process outcome or impact based on a proposed change
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0202 Market predictions or forecasting for commercial activities
• CPC Class Codes: G06Q 30/0203 Market surveys; Market polls
• CPC Class Codes: G06Q 30/0247 Calculate past, present or future revenues
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes

Abstract

The present invention applies a novel iterative algorithm to the problem of multidimensional optimization by supplying a strict, nonlinear mathematical solution to what has traditionally been treated as a linear multidimensional problem. The process consists of randomly selecting a statistically significant sample of a prospect list, calculating the value of the utility function for each pair of an offer and selected prospects, reducing the original linear multidimensional problem to a non-linear problem with a feasible number of dimensions, solving the non-linear problem for the selected sample numerically with the desired tolerance using an iterative algorithm, and using the results to calculate an optimal set of offers in one pass for the full prospect list.

Claims

1. A computer-implemented method for optimizing a cross-selling marketing campaign that includes j=1 to M promotions, targeting i=1 to N customers, said method calculating an N×

M solicitation matrix A=(a_ij), where each a_ij is to be set to a first value when said specific promotion j is to be offered to said specific customer i, or otherwise is to be set to a second value, and comprising the steps of;

(a) accessing a customer database and randomly selecting a statistically significant sample of n customer records from N customer records;

(b) calculating an n×

M response matrix R=(r_ij), where each r_ij is the probability that a specific customer i within said n customers will respond to a specific promotion j;

(c) calculating an n×

M profitability matrix P=(p_ij), where each p_ij is the profitability of said specific customer i when they positively respond to said specific promotion j;

(d) selecting a utility function that is a function of at least said response, profitability and solicitation matrices, said utility function being linear with respect to a_ij;

(e) defining a set of N×

K customer constraint inequalities, C_ik(A)≦

0, wherein K is the total number of customer constraints;

C_ik are linear functions with respect to a_ij; and

each of k=1 to K constraints is reflective of a constraint selected from the group consisting of;

an eligibility condition constraint, a peer group logic constraint and a maximum number of offers constraint;

(f) defining a set of Q economic constraint inequalities, G_q(A, R, P)≦

0, wherein Q is the total number of economic constraints;

G_q are linear functions with respect to a_ij; and

each of q=1 to Q constraints is reflective of an economic goal of the cross-selling marketing campaign, and thus formulating an integer optimization problem with n×

M variables;

(g) deriving a non-linear problem that is mathematically equivalent to said integer optimization problem having Q dimensions;

(h) iteratively solving said non-linear problem on said sample of n customer records within a pre-defined tolerance; and

(i) accessing said customer database and using the solution of the said non-linear problem to calculate each a_ij of said N×

M solicitation matrix A, wherein the values set for each a_ij within said solicitation matrix A is a solution to said integer optimization problem;

wherein at least one of steps (a) through (i) is performed by a computer.

2. The method of claim 1 wherein M is in the order of magnitude of 10³.

3. The method of claim 1 wherein N is in the order of magnitude of 10⁸.

4. The method of claim 1, wherein said first value is 1 and said second value is 0.

5. The method of claim 1, wherein said pre-defined tolerance is about 0.1%.

6. The method of claim 1, wherein said utility function selected in step (d) is a net present value (NPV) function expressed as:

NPV(A, R, P).

7. The method of claim 6, wherein step (h) is accomplished by formulating a min-max problem using a LaGrange multiplier technique.

8. The method of claim 7, wherein said min-max problem is expressed as:

Min<sub>j{Lb>

0,Lc}</sub> Max<sub>j{C<

=0}</sub> ANPV_j(L, r_i, p_i);

wherein ANPV(L, r_i, p_i)=NPV_j(L, r_i, p_i)+L_bG_b(A, R, P)+L_c G_c(A, R, P); and

wherein each of L_b is the inequality component of a LaGrange multiplier, and each of L_c is the equality component of said LaGrange multiplier.

9. The method of claim 8, wherein step (h) is accomplished by iteratively solving said min-max problem by performing at least the following steps:

calculating an initial value of said ANPV function and a gradient vector;

setting an initial value;

setting each of Q number of LaGrange multipliers to said initial value of said ANPV function divided by the square of said gradient vector;

making a step along said gradient vector;

updating said step size when needed;

calculating a new value of said ANPV function taking said set of K constraints into account; and

determining whether there is convergence within said pre-defined tolerance.

10. The method of claim 8, wherein step (i) is accomplished in a single pass through said N customer records by performing the following steps for each of said N customers:

reading a customer record i;

calculating vectors r_i and p_i;

calculating anpv_i=ANPV_j(L, r_i, p_i); and

using said calculated value of anpv_i and said k=1 to K constraints to calculate said solicitation matrix vector a_i=(a_ij).