Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources

Network Revenue Management (NRM) describes a general online allocation problem in which combinations of capacity-constrained resources are sold to a stream of arriving customers. Existing papers propose one-size-fits-all approaches for controlling the capacities of these different resources over time. In this paper, we show that certain network structures can be exploited to improve both theoretical and empirical performance over the existing approaches. Specifically, we study networks with a matroid sub-structure, which can be motivated by many classical supply chain constraints involving postponement and process flexibility.Overall, we introduce a recipe which first uses a heuristic to "bifurcate" the constraints of a given NRM instance into matroid vs. non-matroid ones, and then derive an NRM policy to simultaneously handle these two types of constraints. Our policy has an approximation guarantee of 1/(2(1+L')), where L' denotes the maximum number of non-matroid resources demanded by a customer. This improves the existing 1/(1+L)-approximation for NRM, where a customer can demand up to L total resources, as long as L' is sufficiently smaller than L, as is the case in the aforementioned supply chain applications. Additionally, our framework generalizes these approximations for NRM to the well-motivated reusable resources setting.Finally, we conduct numerical experiments both in the process flexibility setting where the constraints have an explicit bifurcation, and on randomly-generated NRM instances for which we must use our heuristic to bifurcate the constraints. Our framework significantly improves empirical performance in the first setting, by using a matroid to capture what would normally require an exponential number of constraints. On the randomly-generated instances, we show that bifurcating policies still outperform their one-size-fits-all counterparts, even when the number of resources bifurcated using our heuristic is small