US 8,285,577 B1Grant

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

Issue Date:2012-10-09

•17 Claims

•5 Drawing Sheets

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.

Metadata

Assignee

Experian Information Solutions, Inc.

Inventors

Yuri Galperin
Vladimir Fishman
Leonid Gibiansky

Application Information

Application Number:US 13/190,832

Filing Date:2011-07-26

Priority Date:1999-08-06

Art Unit:3623

Classifications

IPC:

G06Q10/00

Patent Drawings (5 sheets)

Description

Relationship to Other Applications

[0001] This application is a continuation of U.S. application Ser. No. 09/634,624 filed Aug. 5, 2000, now pending, which claims the benefit of priority of U.S. Provisional Application Ser. No. 60/147,456 filed Aug. 6, 1999, now abandoned. The disclosures of the foregoing applications are incorporated by reference.

Field of the Invention

[0002] This invention relates generally to the development of a method to optimize the effects of cross-selling marketing campaigns. More specifically, this invention is an improvement on the application of classical methods of discrete linear programming to the problem of multidimensional optimization.

Background Of. Me Invention

[0003] Businesses typically have a number of promotions to offer to a large list of prospective customers. Each promotion may have an eligibility condition, a response model, and a profitability model associated with it.

[0004] Some promotions may be combined into Peer Groups (i.e., groups of mutually exclusive offers, such as a credit card with different interest rates). A constraint may be placed on the maximum number of offers that goes to any customer; in addition, there may be business requirements such as minimal number of sales, minimal NPV (Net Present Value) per customer, maximal budget, etc. These requirements may apply to any individual promotion, a peer group, or a campaign as a whole.

[0005] The goal of cross-selling marketing optimization is to determine what offers to send to which customers to maximize a utility function of the campaign (total NPV, total number of sales etc.), while satisfying all the business requirements and constraints.

[0006] The present state of the art lets marketers process one offer at a time. A response and/or profitability model is applied and customers are rank-ordered based on propensity to respond to the offer. After this ordering, a certain percentage from the top of the list is selected to receive the offer. The same process is applied to all available offers separately.

[0007] As a result, the best, most responsive and valuable customers are saturated with offers and the middle segment of the customer list is ignored. The overall efficiency of the campaign therefore degrades.

[0008] Another significant drawback of this approach is the inability to satisfy various real-life constraints and business goals.

[0009] Most sophisticated marketers have tried to consolidate models built for different offers. However, these attempts have not been based on any solid scientific method, but rather have utilized an ad hoc approach. Because of this, only the most-simple constraints have been able to be satisfied and the solutions have been sub-optimal with respect to a utility function. In fact, these marketers haven't even been able to estimate how far off they are from the true optimum.

[0010] What would therefore be useful is a process that provides a mathematically optimal offer allocation, i.e., one that selects an optimal set of offers for each customer that maximizes the utility function and satisfies all business goals and constraints.

Summary of the Invention

[0011] The present invention represents the application of a novel iterative algorithm to the problem of multidimensional optimization. The present invention supplies a strict, nonlinear mathematical solution to what has traditionally been treated as a linear multidimensional problem.

[0012] The problem in its original form is a problem of discrete linear programming. However, due to a huge number of dimensions (in a typical business case N=O(10⁸), M=O(10²)), the application of classical methods of discrete linear programming is not feasible.

[0013] The process of the present invention 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.

[0014] It is an object of the present invention to increase the efficiency of a cross-selling marketing campaign.

[0015] It is an object of the present invention to increase the efficiency of cross-selling campaigns that include a large number of offers.

[0016] It is an object of the present invention to provide optimization of cross-selling campaigns wherein groups of offers can be mutually exclusive.

[0017] It is an object of the present invention to increase the efficiency of cross-selling campaigns that are targeted to large number of prospective customers.

[0018] It is an object of the present invention to increase the efficiency of cross-selling campaigns by selecting an individual, optimal set of offers for each customer.

[0019] It is an object of the present invention to constrain of maximum number of offers sent to a customer within cross-selling campaigns.

[0020] It is an object of the present invention to satisfy business goals, like minimum number of sales and budget constraints, while optimizing cross-selling campaigns as applied to individual offers, groups of offers or the entire campaign.

[0021] It is an object of the present invention to maximize a user-chosen utility function, like total NPV or number of sales, within a cross-selling campaign.

[0022] It is an object of the present invention to mathematically maximize the utility function and satisfy all constraints within a cross-selling campaign.

[0023] It is an object of the present invention to allow interactive changes in goals or constraints of cross-selling campaigns and quickly view the results.

[0024] It is an object of the present invention to provide final scoring for cross-selling campaigns in a single pass so as to scalable and efficient enough to process a list of 100 million customers overnight.

[0025] It is yet another object of the invention to provide true “one-to-one” marketing in cross-selling campaigns.

Brief Description of the Drawings

[0026] FIG. 1 is a flow chart of the basic process of the present invention.

[0027] FIG. 2 is a more detailed data flow of a marketing optimization process of the present invention.

[0028] FIG. 3 is a flow chart of the single pass process of the present invention.

[0029] FIG. 4 is a flow chart of the novel iterative algorithm of the present invention.

Detailed Description of the Invention

[0030] The present invention represents the application of a novel iterative algorithm to the problem of multidimensional optimization of cross-selling campaigns by supplying a strict, nonlinear mathematical solution to the traditional linear multidimensional problem desired to be solved when offering a large number of promotions M to a very large set of prospective customers N.

[0031] The process of the present invention, as shown in FIG. 1, consists of randomly selecting a statistically significant sample 10 of a prospect list, calculating the value of the utility function 20 for each pair of an offer 30 and selected prospects 10, reducing the original linear multidimensional problem to a non-linear problem 40 with a feasible number of dimensions, solving the non-linear problem 50 for the selected sample numerically with the desired tolerance using an iterative algorithm, and using the results to calculate an optimal set of offers 60 in one pass for the full prospect list.

[0032]

Let A = (a_{ij}), be a solicitation matrix, where

\begin{matrix} a_{ij} = 1, if offer j goes to a customer i \\ = 0, otherwise; \end{matrix}

- [0033] R=(r_ij), be a response matrix, where
  - [0034] r_ij—is a probability for a customer i respond to a promotion j;
- [0035] P=(p_ij), be a profitability matrix, where
  - [0036] p_ij—is a profitability of a customer i, if he/she responds to a promotion j.

[0037] Total NPV of the campaign, NPV=NPV(A, R, P), is a linear function of a_ij, r_ij, p_ijand other economic parameters of the campaign.

[0038] Eligibility conditions, peer group logic, and maximal number of offers per customer constraint can be expressed by a set of inequalities C_ik
C_ik(A)<=0, i=1,2, . . . ,N, k=1,2, . . . ,K

[0039] where C, are linear functions, and N is of the order of number of customers in the prospect list, K is number of restrictions. These customer-level restrictions are applied for each individual. Economic goals are expressed by a set of inequalities G for each promotion and the whole campaign:
G_j,l(A,R,P)<=0, j=1,2, . . . ,M, l=1,2, . . . ,L_j
G_0,l(A,R,P)<=0, l=1,2, . . . ,L₀

[0040] where are linear functions, and M is of the order of number of promotions in the campaign, L_jis total number of restrictions. These main restrictions are applied for a promotion or the campaign, and G is a sum over all eligible customers.

[0041] It is desired to then find a solicitation matrix A that maximizes NPV(A,*) under the condition that all constraints C and G are satisfied.

[0042] The solution presented by the inventors uses the following steps, as shown in FIG. 2. A first step is to create a campaign or project by selecting a set 202 of targeting optimizer (TO) projects from a modeling database 200. Each TO project contains promotion and offer economics, and eligibility information for a selected pool of prospects. Each TO project includes substitute offer groups 206, model calibration 204, and eligibility information that is combined with the prospect input to create an eligibility matrix 214.

[0043] For prospect input, one selects, randomly, a statistically significant sample or testing DCP (derived customer pool) 212 of a prospect list from a customer database 210. Matrices P and R are then calculated for selected prospects at 224. The next steps, to reduce the original linear multidimensional problem to a non-linear problem with a feasible number of dimensions and solve the non-linear problem for the selected sample numerically with the desired tolerance using a novel iterative algorithm (described below) is done by the optimization engine 240.

[0044] Input data reports 230 record the matrices and offers used. Using this input data, campaign level constraints 242, and offer level constraints 244, the optimization engine 240 produces a solicitation matrix 250. This is used to calculate report data 252 for optimization reports 254 that are tested at 260 to see if the selected constraints 242 and 244 satisfied the desired offer solicitation schema 256. If satisfied, a final report 260 is generated. If the offer solicitation schema 256 are not satisfied, campaign level constraints 242 and offer level constraints 244 are adjusted to produce another iteration.

[0045] The optimization engine 240 calculates the vector of parameters L of the ANPV (adjusted NPV) functions
ANPV_j(L,r_i,p_i),

[0046] where

- [0047] j=1, 2, # of promotions;
- [0048] r_i=(r_ij)—vector of propensities to respond of a customer i to promotions 1, 2, . . .
- [0049] p_i=(p_ij)—vector of profitability of a customer i for promotions 1, 2, . . .

[0050] It then calculates the optimal solicitation matrix 250 in a single pass through the full prospect list. To accomplish that, as shown in FIG. 3:

- [0051] 1. Read the next customer record 31;
- [0052] 2. Calculate vectors r, and p_i32;
- [0053] Calculate anpv_i=(ANPV_j(L, r_i, p_i), j=1, 2, . . . , # of promotions) 33;
- [0054] 4. Based on the values of anpv_iand eligibility conditions, calculate solicitation vector
  - [0055] a_i=(a_ij, j=1, 2, . . . , . . . , # of promotions), which defines the optimal set of promotions that goes to a customer i at 34; and
- [0056] 5. Repeat the previous four steps until the end of the customer list at 35.

[0057] To calculate matrices P and R for selected prospects at 224 and reduce the original linear multidimensional problem to a non-linear problem with a feasible number of dimensions described above, the present invention needs to solve the high dimensional conditional extremum problem with a large number of restrictions. The present invention uses the Lagrange multiplier technique to take into account only the main restrictions. They can be of an equality or inequality type. This low-dimensional nonlinear problem is solved by a gradient type iterative process.

[0058] At each iterative step, the optimization of ANPV_j(L, r_i, p_i) under customer-level restrictions (high dimensional linear problem) is made directly, record by record. It is equivalent to the following min-max problem:
Min_j{Lb>0,Lc}Max_j{C>=0}ANPV(L,r_i,p_i),

[0059] where ANPV(L, r_i, p_i)=ANPV(L, r_i, p_i)₀+L_bG_b(A, R, P)+L_cG_c(A, R, P)

[0060] Here, summation over all the inequalities is assumed.

[0061] The algorithm, as shown in FIG. 4, consists of following steps:

[0062] 1. Prepare data 41.
[0063] 2. Calculate initial value of the functional and gradients 42.
[0064] 3. Set a value for initial algorithm steps 43; for each Lagrange multiplier, the step should be set equal to the initial value of the functional divided by the square of the gradient.
[0065] 4. Make a step along the gradient 44.
[0066] 5. Update the step 45, if needed.
[0067] 6. Calculate new value of the functional 46, taking customer level restrictions into account.
[0068] 7. Check convergence 47.
[0069] 8. If not converged at 48, go to step 4.
[0070] 9. Output the results 49 upon adequate convergence.

[0071] It is important to underscore that the above algorithm is not a heuristic, but delivers a strict mathematical solution for the multidimensional optimization problem formulated above.

[0072] Tests performed by inventors on a variety of real business cases show that the iterative procedure in Step 4 above typically converges with the tolerance of 0.1% in less then 30 iterations. That allows a user to work with the cross-selling optimizer of the present invention interactively and perform real-time analysis of the financial outcome of marketing activities.

[0073] A novel feature of the algorithm used by the present invention, the one-pass scoring, enables rollout scoring of a 100 M record database overnight.

[0074] The present invention operates on a computer system and is used for targeted marketing purposes. Using the present invention in conjunction with a neural network, the present invention provides a user with data indicating the individuals or classes or individuals who are most likely to respond to direct marketing.

Claims

We claim:

1. A method comprising:

at least one computer processor formulating a linear optimization problem with a plurality of variables and that takes into account at least:

a plurality of customer constraints stored in computer storage and comprising at least one of an eligibility condition constraint, a peer group logic constraint, and a maximum number of offers constraint; and

a plurality of economic, business, or consumer constraints stored in computer storage, wherein each constraint is reflective of an economic goal of a business to consumer decisioning strategy;

the computer processor reducing the linear optimization problem to a non-linear problem with a feasible number of dimensions, wherein the non-linear problem is mathematically equivalent to the linear optimization problem; and

the computer processor selecting a business to consumer decisioning strategy with desired expected utility and that satisfies the constraints at least in part by iteratively solving the non-linear problem on a sample of customers within a pre-defined tolerance, wherein the selected consumer decisioning strategy identifies specific customers that are to receive specific decision options, and wherein the non-linear problem takes into account at least:

a plurality of behavioral probabilities that each represent a probability that a specific customer will respond to a specific decision option; and

a plurality of profitabilities that each represent a profitability resulting from a specific customer responding to the specific decision option.

2. The method of claim 1, wherein selecting a strategy with desired expected utility comprises selecting a strategy that is expected to have a higher value than another business to consumer decisioning strategy.

3. The method of claim 1, wherein selecting a strategy with desired expected utility comprises selecting a utility function and using the utility function to calculate an expected utility of the strategy.

4. The method of claim 1, wherein the customer constraints are expressed as linear functions.

5. The method of claim 4, wherein the economic and business constraints are expressed as linear functions.

6. The method of claim 1, wherein the customer constraints are expressed as at least one inequality.

7. The method of claim 6, wherein the economic and business constraints are expressed as at least one inequality.

8. The method of claim 1, wherein selecting a strategy with desired expected utility further comprises generating a plurality of solicitation values that define which customers receive which decision options.

9. A decisioning strategy optimization system comprising:

a computer processor configured to execute software components;

at least one data repository of computer storage containing at least one collection of data comprising:

customer data related to a plurality of customers;

behavioral probability data representing a plurality of probabilities that a specific customer will respond to a specific decision option;

profitability data representing, for each of a plurality of customers, value resulting from a specific customer responding to a specific decision option;

customer constraint data representing a plurality of customer constraints, wherein the customer constraints comprise at least one of an eligibility condition constraint, a peer group logic constraint, and a maximum number of offers constraint; and

economic constraint data representing a plurality of economic constraints, wherein each economic constraint is reflective of an economic goal of a decisioning strategy;

a first software component configured to cause the computer processor to formulate a linear optimization problem with a plurality of variables;

a second software component configured to cause the computer processor to reduce the linear optimization problem to a substantially equivalent non-linear problem with a feasible number of dimensions; and

a third software component configured to cause the computer processor to select a decisioning strategy with desired expected utility and that satisfies stored customer and economic constraints at least in part by iteratively solving the non-linear problem on a sample of customers within a pre-defined tolerance, wherein the non-linear problem takes into account at least some of the stored behavioral probabilities and stored profitabilities and the decisioning strategy identifies specific customers that are to receive specific decision options.

10. The system of claim 9, wherein the at least one data repository comprises at least one database.

11. The system of claim 9, wherein the third software component is configured to select a decisioning strategy with desired expected utility by selecting a decisioning strategy that is expected to have a business value that is higher than another decisioning strategy.

12. The system of claim 9, wherein the second software component selects a decisioning strategy with desired expected utility by selecting a utility function and using the utility function to calculate an expected utility of the decisioning strategy.

13. The system of claim 9, wherein the customer constraints are expressed as linear functions.

14. The system of claim 12, wherein the economic constraints are expressed as linear functions.

15. The system of claim 9, wherein the customer constraints are expressed as at least one inequality.

16. The system of claim 15, wherein the economic constraints are expressed as at least one inequality.

17. The system of claim 9, wherein the second software module is further configured to generate and store in the at least one data repository a plurality of solicitation values that define which customers receive which decision options.

Patent Citations (60)

Patent	Date	Inventor	Cited By
US5201010(A)	1993-04-01	Deaton et al.	Applicant
US6044357(A)	2000-03-01	Garg	Applicant
US6208979(B1)	2001-03-01	Sinclair	Applicant
US6236977(B1)	2001-05-01	Verba et al.	Applicant
US6334110(B1)	2001-12-01	Walter et al.	Applicant
US6412012(B1)	2002-06-01	Bieganski et al.	Applicant
US6640215(B1)	2003-10-01	Galperin et al.	Applicant
US6959281(B1)	2005-10-01	Freeling et al.	Applicant
US6993493(B1)	2006-01-01	Galperin et al.	Applicant
US7275083(B1)	2007-09-01	Seibel et al.	Applicant
US7366694(B2)	2008-04-01	Lazerson	Applicant
US7424439(B1)	2008-09-01	Fayyad et al.	Applicant
US7472088(B2)	2008-12-01	Taylor et al.	Applicant
US7499868(B2)	2009-03-01	Galperin et al.	Applicant
US7571139(B1)	2009-08-01	Giordano et al.	Applicant
US7580856(B1)	2009-08-01	Pliha	Applicant
US7590589(B2)	2009-09-01	Hoffberg	Applicant
US7610257(B1)	2009-10-01	Abrahams	Applicant
US7653592(B1)	2010-01-01	Flaxman	Applicant
US2002/0023051(A1)	2002-02-01	Kunzle et al.	Applicant
US2002/0082892(A1)	2002-06-01	Raffel et al.	Applicant
US2002/0128960(A1)	2002-09-01	Lambiotte et al.	Applicant
US2003/0033242(A1)	2003-02-01	Lynch et al.	Applicant
US2003/0036996(A1)	2003-02-01	Lazerson	Applicant
US2003/0216965(A1)	2003-11-01	Libman	Applicant
US2003/0233323(A1)	2003-12-01	Bilski et al.	Applicant
US2004/0107125(A1)	2004-06-01	Guheen et al.	Applicant
US2004/0163101(A1)	2004-08-01	Swix	Applicant
US2005/0209922(A1)	2005-09-01	Hofmeister	Applicant
US2005/0251820(A1)	2005-11-01	Stefanik et al.	Applicant
US2006/0004731(A1)	2006-01-01	Seibel et al.	Applicant
US2006/0041443(A1)	2006-02-01	Horvath	Applicant
US2006/0080233(A1)	2006-04-01	Mendelovich et al.	Applicant
US2006/0080251(A1)	2006-04-01	Fried et al.	Applicant
US2006/0229943(A1)	2006-10-01	Mathias et al.	Applicant
US2006/0242039(A1)	2006-10-01	Haggerty et al.	Applicant
US2006/0242046(A1)	2006-10-01	Haggerty et al.	Applicant
US2006/0242050(A1)	2006-10-01	Haggerty et al.	Applicant
US2007/0033227(A1)	2007-02-01	Gaito et al.	Applicant
US2007/0192165(A1)	2007-08-01	Haggerty et al.	Applicant
US2007/0226130(A1)	2007-09-01	Haggerty et al.	Applicant
US2007/0244732(A1)	2007-10-01	Chatterji et al.	Applicant
US2007/0282684(A1)	2007-12-01	Prosser et al.	Applicant
US2007/0288271(A1)	2007-12-01	Klinkhammer	Applicant
US2008/0059317(A1)	2008-03-01	Chandran et al.	Applicant
US2008/0120155(A1)	2008-05-01	Pliha	Applicant
US2008/0177836(A1)	2008-07-01	Bennett	Applicant
US2008/0228635(A1)	2008-09-01	Megdal et al.	Applicant
US2008/0255897(A1)	2008-10-01	Megdal et al.	Applicant
US2008/0294540(A1)	2008-11-01	Celka et al.	Applicant
US2009/0018996(A1)	2009-01-01	Hunt et al.	Applicant
EP1122664	2001-08-01		Applicant
WO99/04350	1999-01-01		Applicant
WO99/22328(A1)	1999-05-01		Applicant
WO/55789(A2)	2000-09-01		Applicant
WO/55790(A2)	2000-09-01		Applicant
WO1/11522(A2)	2001-02-01		Applicant
WO1/75754	2001-10-01		Applicant
WO3/101123	2003-12-01		Applicant
WO2007/149941	2007-12-01		Applicant

Non-Patent Literature (12)

Jost, Allen; “Neural Networks”; Credit World, vol. 81, No. 4, pp. 26-33, Mar./Apr. 1993.Applicant
Egol, Len; “What's New in Database Marketing Software”; Direct, vol. 6, No. 8, p. 39(4), Aug. 1994.Applicant
Sweat, Jeff; “Know Your Customers”; Information Week, p. 20, Nov. 30, 1998.Applicant
Fusun Gonul et al., “Optimal Mailing of Catalogs: A New Methodology Using Estimable Structural Dynamic Programming Models”, 14 pages, Management Science, vol. 44, No. 9, Sep. 1998.Applicant
GR Bitran, SV Mondschein—Management Science, 1996—JSTOR Mailing Decisions in the Catalog Sales Industry, Gabriel R. Bitram, Susana V. Mondschein. Management Sciencem vol. 42, No. 9, 1364-81, Sep. 1996.Applicant
Hakan Polatoglua and Izzet Sahinb, Probability distributions of cost, revenue and profit over a warranty cycle, European Journal of Operational Research, vol. 108, Issue 1. Jul. 1, 1998, p. 170-83.Applicant
Haughton, Dominique et al., “Direct Marketing Modeling with CART and CHAID”, Journal of Direct Marketing, vol. 11, No. 4, Fall 1997, p. 42-52.Applicant
Jan Roelf Bult et al., “Optimal Selection for Direct Mail”, Marketing Science, vol. 14, No. 4, 1995, pp. 378-394.Applicant
Muus, Lars et al., “A decision theoretic framework for profit maximization in direct marketing”, 20 pages, Sep. 1996.Applicant
Pieter Otter et al., “Direct mail selection by joint modeling of the probability and quantity of response”, 14 pages, Jun. 1997.Applicant
Schmittlein, David C. et al., “Customer Base Analysis: An Industrial Purchase Process Application”, Marketing Science, vol. 13, No. 1 (Winter 1994), p. 41-67.Applicant
Lamons, Bob; Be Smart: Offer Inquiry Qualification Services, Marketing News, Nov. 6, 1995, vol. 29, No. 23, ABI/Inform Global, p. 13.Applicant

Abstract