Contributions published at Mathematics for Economists (Christiane Barz)

We suggest a novel choice of non-separable basis functions for an approximate linear programming approach to the well-known network revenue management problem. Considering non-separability is particularly important when interdependencies between resources are large. Such a situation can be illustrated for example by a bus line, where different origin-destination pairs have many overlapping segments. Traditional separable approximation approaches tend to ignore the resulting interactions. We suggest to group resources into non-separable subnetworks. For each chosen subnetwork, basis functions either span the whole function space or consist of linear functions. Given this more general choice of basis functions, we extend existing reductions of approximate linear programs. If there is only one subnetwork, for which the basis functions span the whole function space, we prove the equivalence to a compact linear program of polynomial size. For the general case, we suggest an approximate reduction. Numerical examples illustrate our novel upper bounds for the maximum expected revenue and the corresponding competitive policies. In particular, we find that the added benefit of non-separability heavily depends on the network structure and the capacity. Our work helps to better understand the impact of assuming separability in network revenue management. The polynomial sized reductions make it possible to estimate the added average revenue resulting from incorporating interactions between resources. The theory we develop demonstrates how the interpretation of dual variables as state-action probabilities can be applied to reduce exponentially large approximate linear programs via variable aggregation.

We are concerned with computing bid prices in network revenue management using approximate linear programming. It is well-known that affine value function approximations yield bid prices which are not sensitive to remaining capacity. The analytic reduction to compact linear programs allows the efficient computation of such bid prices. On the other hand, capacity-dependent bid prices can be obtained using separable piecewise linear value function approximations. Even though compact linear programs have been derived for this case also, they are still computationally much more expensive compared to using affine functions. We propose compact linear programs requiring substantially smaller computing times while, simultaneously, significantly improving the performance of capacity-independent bid prices. This simplification is achieved by taking into account remaining capacity only if it becomes scarce. Although our proposed linear programs are relaxations of the unreduced approximate linear programs, we conjecture equivalence and provide according numerical support. We measure the quality of an approximation by the difference between the expected performance of an induced policy and the corresponding theoretical upper bound. Using this paradigm in numerical experiments, we demonstrate the competitiveness of our proposed linear programs.

We consider a real discrete pricing problem in network revenue management for FlixBus. We improve the company's current pricing policy by an intermediate optimization step using booking limits from standard deterministic linear programs. We pay special attention to computational efficiency. FlixBus' strategic decision to allow for low-cost refunds might encourage large group bookings early in the booking process. In this context, we discuss counter-intuitive findings comparing booking limits with static bid price policies. We investigate the theoretical question whether the standard deterministic linear program for network revenue management does provide an upper bound on the optimal expected revenue if customer's willingness to pay varies over time.

null

null

null

null

null

null

null

null

null

null

null

null

null

null

null