Department Colloquium - Dan Zhang

Dan Zhang, Leeds School of Business, University of Colorado Boulder

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)


Friday, January 25, 2019 at 3:00pm to 4:00pm

Engineering Center, ECCR 265
1111 Engineering Drive, Boulder, CO 80309

Event Type



Science & Technology, Research & Innovation


General Public

College, School & Unit

Engineering & Applied Science

Applied Mathematics
Google Calendar iCal Outlook