Product Promotion Optimization System

A system that determines promotional pricing for a product and for an objective function receives a non-linear time-dependent optimization problem for the product, where the non-linear problem includes a demand model and a plurality of constraints, and the constraints include a price ladder that includes a plurality of time periods and a non-promotional price for the product at each time period. For each of the time periods, the system determines a change in the objective function when the price at the time period includes a promotional price and all other prices on the price ladder are set to the non-promotional price to generate coefficients. The system determines a maximum value of the coefficients at each time period and generates an approximate Mixed Integer Programming ("MIP") problem based on the coefficients. The system determines a Linear Programming ("LP") relaxation of the MIP problem and solves the LP relaxation.