In this paper, we propose a randomized linear program to obtain bid prices for the network revenue management problem with customer choice behavior. Our development proceeds in two stages. We first formulate a mixed integer program that can be viewed as a deterministic approximation to the network revenue management problem. We then use the optimal solution to the mixed integer program to formulate a linear program that can be easily randomized. We establish that our solution
method approximates the optimal total expected revenue arbitrarily closely in an asymptotic regime where the leg capacities and the number of time periods in the decision horizon increase linearly with the same rate. Numerical experiments indicate that our approach may be a viable alternative to the standard deterministic linear program that appears in the existing literature.