  This paper addresses a novel data science problem, prescriptive price
optimization, which derives the optimal price strategy to maximize future
profit/revenue on the basis of massive predictive formulas produced by machine
learning. The prescriptive price optimization first builds sales forecast
formulas of multiple products, on the basis of historical data, which reveal
complex relationships between sales and prices, such as price elasticity of
demand and cannibalization. Then, it constructs a mathematical optimization
problem on the basis of those predictive formulas. We present that the
optimization problem can be formulated as an instance of binary quadratic
programming (BQP). Although BQP problems are NP-hard in general and
computationally intractable, we propose a fast approximation algorithm using a
semi-definite programming (SDP) relaxation, which is closely related to the
Goemans-Williamson's Max-Cut approximation. Our experiments on simulation and
real retail datasets show that our prescriptive price optimization
simultaneously derives the optimal prices of tens/hundreds products with
practical computational time, that potentially improve 8.2% of gross profit of
those products.
