US 7,689,528 B2 · Method and apparatus for a scalable algorithm for decision optimization

Abstract

An iterative approach to solving the optimization problem is provided. The invention provides an iteration of four basic operations; determining the segments, balancing the segments, expanding a segment, and solving the segment optimization. The method and apparatus can use any off-the-shelf linear programming (LP) solver, such as Dash Optimization Xpress, by Dash Optimization, during the solve operation. The size of the problem fed into the LP solver remains bounded and relatively small compared to the entire problem size. Thus, the algorithm can solve problems of several orders of magnitude larger. In one embodiment of the invention, the sampling and segmentation techniques are removed to where the problem is solved at the account-level. In the above cases, the solution is produced in a more cost-effective manner and the best possible return is achieved because the doubt of achieving a true global solution is removed.

A computer implemented method for generating a tangible machine-readable record representing a solution for a decision optimization problem corresponding to a marketing campaign of an enterprise, the method performed by one or more computer processors based on a plurality of computer instructions, the instructions comprising:

initiating, by one or more of the computer processors, a determination of a global solution to a decision optimization problem applied to a set of original account data representing real world entities associated with the marketing campaign, the set of account data including multiple rows where each row represents an account, where the problem includes at least one sub-problem posed to every account and the problem also includes global constraints acting on all accounts;
preparing, by one or more of the computer processors, an initial solution to the decision optimization problem, the initial solution including a sub-solution to the sub-problem for each account, and setting the initial solution as a current solution, the current solution being assigned without considering the global constraints acting on all accounts;
establishing, by one or more of the computer processors, a row partition grouping the rows data into segments based on said current solution, each segment representing an aggregation of rows, a first portion of the segments being non-fractional segments and a second portion of the segments being fractional segments, the fractional segments comprising more than one element and the non-fractional segments comprising only one element;
balancing, by one or more of the computer processors, said row partition at least by partitioning any non-fractional segments larger than a predetermined size and, at least by combining any pair of two non-fractional segments wherein the pair's size is smaller than the predetermined size;
expanding, by one or more of the computer processors, one or more selected non-singleton segments of said balanced row partition that are not already designated as expanded, and designating the selected segments as expanded, the non-singleton statements each containing more than one element;
computing, by one or more of the computer processors, a new solution to the decision optimization problem as presented by the partitioned, balanced, and expanded account data, where the new solution includes (1) a sub-solution to the sub-problem for each account of the expanded segments, and (2) a sub-solution to the sub-problem for each segment other than the expanded segments;
determining, by one or more of the computer processors, if said new solution is nearer to an optimal solution than the current solution,
if YES, then designating the new solution to be the current solution, and repeating the establishing, balancing, expanding, and computing operations using rows of the partitioned, balanced, and expanded partition instead of the rows of the original account data,
if NO, performing the following:
(1) if there are any non-singleton segments in said balanced row partition not designated as expanded, then repeating the expanding and computing operations;
(2) if all non-singleton segments of said balanced row partition have been designated as expanded, then storing a database comprising a machine-readable record of a latest version of new solution.

8 more elements

Method and apparatus for a scalable algorithm for decision optimization

Life of this patent

Method and apparatus for a scalable algorithm for decision optimization

Life of this patent

Abstract

Claims8