A randomized linear programming method for computing network bid prices

Kalyan Talluri

doi:10.1287/trsc.33.2.207

Return

A randomized linear programming method for computing network bid prices

1999-05-01

145

PRE

Kalyan Talluri

Garrett van Ryzin

DOI：10.1287/trsc.33.2.207

Original

Original request for help

Save

Abstract

En 中文

We analyze a randomized version of the deterministic Linear programming (DLP) method for computing network bid prices. The method consists of simulating a sequence of realizations of itinerary demand and solving deterministic linear programs to allocate capacity, to itineraries for each realization. The dual prices from this sequence are then averaged to form a bid price approximation This randomized linear programming (RLP) method is only slightly more complicated to implement than the DLP method. We show that the RLP method can be viewed as a procedure for estimating the gradient of the expected perfect information (PI) network revenue. That is, the expected revenue obtained with full information on future demand realizations. The expected PI revenue can, in turn, be viewed as an approximation to the optimal value function. We establish conditions under which the RLP procedure provides an unbiased estimator of the gradient of the expected PI revenue. Computational tests are performed to evaluate the revenue performance of the RLP method compared to the DLP.

Keywords:

FARE CLASSES

MODEL

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.