Finite-Horizon Approximate Linear Programs for an Infinite-Horizon Revenue Management Problem
Approximate linear programs have been used extensively to approximately solve stochastic dynamic programs that suffer from the well-known curse of dimensionality. Due to canonical results establishing the optimality of stationary value functions and policies for infinite-horizon dynamic programs, the literature has largely focused on approximation architectures that are stationary over time. In a departure from this literature, we apply a non-stationary approximation architecture to an infinite-dimensional linear programming formulation of the stochastic dynamic programs. We solve the resulting problems using a finite-horizon approximation. Such finite-horizon approximations are common in the theoretical analysis of infinite-horizon linear programs, but have not been considered in the approximate linear programming literature. We illustrate the approach on a rolling-horizon revenue management problem using an affine approximation architecture. We obtain two main results. First, non-stationary approximations can substantially improve upper bounds on the optimal revenue. Second, we show that the improvement does not come at the expense of tractability, as the resulting approximate linear programs admit compact representations and can be solved efficiently. The resulting approximations also improve heuristic policy performance and dramatically reduce optimality gaps in numerical experiments. (Joint work with Thomas Vossen and Fan You)