A randomized linear programming method for computing network bid prices

A randomized linear programming method for computing network bid prices

0.00 Avg rating0 Votes
Article ID: iaor20011035
Country: United States
Volume: 33
Issue: 2
Start Page Number: 207
End Page Number: 216
Publication Date: May 1999
Journal: Transportation Science
Authors: ,
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.