Mostly OM

Speakers 2018

当前位置: 首页 - Mostly OM - Past Workshops - Speakers 2018 - 正文

Prof. Dan Zhang

发布日期:2024-03-03

点击量:

undefined


Prof. Dan Zhang

University of Colorado


Talk: 

Finite-Horizon Approximate Linear Programs for an Infinite-Horizon Revenue Management Problem


Abstract:

Approximate linear programs (ALPs) 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 nonstationary 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 capacity allocation problem using an affine approximation architecture. We obtain three main results. First, nonstationary approximations can substantially improve upper bounds on the optimal revenue. Second, the upper bounds from the finite-horizon approximation monotonically decrease as the horizon length increases, and converge to the upper bound from the infinite-horizon approximation. Finally, the improvement does not come at the expense of tractability, as the resulting ALPs admit compact representations and can be solved efficiently. The resulting approximations also produce strong heuristic policies and significantly reduce optimality gaps in numerical experiments.





关闭

地址:清华大学经济管理学院伟伦楼447(100084)

邮箱:rccm@mail.tsinghua.edu.cn

电话:010-62771663

传真:010-62784555

Copyright 2025清华大学现代管理研究中心 版权所有