Degeneracy in Network Revenue Management

In network revenue management, the goal is to allocate limited capacities such as seats on airplanes, trips in rail transportation, or vehicles in car rental in a way that maximizes total revenue. A widely used approach for this purpose is bid-price control, which decides whether to accept a request by comparing its revenue with the expected opportunity costs.

However, these methods have a largely overlooked weakness. When the underlying optimization model admits multiple dual solutions, a phenomenon known as primal degeneracy, the resulting bid prices can be ambiguous. This may lead to capacity being consumed by low-profit product requests even though it would be needed later for more profitable bookings.

Our work shows that this phenomenon occurs frequently in network revenue management and explains how it affects the decision quality of classical bid-price methods. In addition, we introduce new control approaches that make optimal decisions even under degeneracy and achieve substantial profit improvements in our experiments.