Randomized Decomposition

OVERVIEW

  • Oracle customers are interested in mathematical optimization for portfolio optimization, vehicle routing, discount optimization, shelf-space optimization, and many other business applications. In these applications, the decision variables are often items (non-negative integers) with a limited number of choices or prices with a limited selection of values. There can be many constraints that express item limits and interactions, finite amount of store or warehouse storage and display space, discount limitations, time horizons, and many other factors. The objective function, which is usually to maximize revenue or profit or to minimize cost, can be highly non-linear due to complex interactions such as price elasticity. For example, a grocery store might choose to discount a particular type of cereal, which should increase the amount of that cereal purchased and may decrease the amount of other types of cereal purchased, but could also lead to increased sales of milk and sugar. The relationship of these econometric substitutes and complements are often expressed as complex exponential functions.

    These kinds of business problems lead to combinatorial mathematical optimization problems, which can in principle be solved by complete enumeration of all possible decision variable value combinations. In practice, of course, there are far too many combinations for complete enumeration to be viable, so techniques such as branch and bound, tabu search, and many kinds of genetic algorithms have been applied to these problems. However, in our testing across several types of these real-world business problems, no single approach seemed to solve all of them to our satisfaction, and classic linear/non-linear programming solvers also struggle to obtain good solutions. The idea of using enumeration led us to consider a different solution approach - decomposing the problem into sub-problems that are small enough to be solved optimally by enumeration or another strategy. Because we had a wide variety of problems to solve, problem structure could not be used to guide the decomposition process as is done in classic approaches such as Bender's or Dantzig-Wolfe decomposition.

    Our insight was to randomly decompose the decision variables into subsets and optimize each of these sub-problems in random order, with the decision variables outside a sub-problem held constant. We call this search technique Randomized Decomposition (RD). RD seems to work well for the combinatorial optimization problems inherent in our products. It has been combined with a large neighborhood search metaheuristic to create complete solution framework, called RDSolver: a general purpose, non-linear, non-convex discrete solver for solving hard, real-world mathematical programs.

    RDSolver has been successfully applied to a wide range of problems, including revenue management problems, graph problems (min/max cut, partitioning and clustering), the traveling salesman problem, and assignment problems. It is currently shipping in Oracle products for project portfolio optimization and vehicle routing. It is also being integrated into additional Oracle products for discount optimization and assortment optimization and is under evaluation for use in other areas.

PUBLICATIONS