Approximate Linear Programming in Network Revenue Management with Multiple Modes

Approximate linear programming has been applied to network revenue management problems under the fundamental modeling assumption that products de?ne combinations of one resource bundle and a fare class. We consider products that can have multiple operational modes allowing companies to select the way they want to serve the purchaser of a multi-mode product. We show that the presence of multi-mode products implies a weaker relation between an a?ne approximate linear program (ALP) and a compact reformulation, known as reduction. Consequently, the upper bound on the maximum expected revenue obtained via the reduction is not necessarily as tight as the upper bound produced via the ALP. We further demonstrate that the gap between these two formulations is bounded in general and zero in a particular class of instances, when multi-mode products are ?exible products. For general instances, we exploit a set-packing structure within the reduction in order to improve the upper bound, i.e., we introduce a cutting plane method that strengthens the reduction by separating valid inequalities. Our computational tests indicate that it is possible to halve the gap in not more than 4% of the time needed to solve the ALP via column generation.