Online stochastic reservation systems

Online stochastic reservation systems

0.00 Avg rating0 Votes
Article ID: iaor200971098
Country: Germany
Volume: 171
Issue: 1
Start Page Number: 101
End Page Number: 126
Publication Date: Oct 2009
Journal: Annals of Operations Research
Authors: , , ,
Keywords: programming: dynamic
Abstract:

This paper considers online stochastic reservation problems, where requests come online and must be dynamically allocated to limited resources in order to maximize profit. Multi-knapsack problems with or without overbooking are examples of such online stochastic reservations. The paper studies how to adapt the online stochastic framework and the consensus and regret algorithms proposed earlier to online stochastic reservation systems. On the theoretical side, it presents a constant sub-optimality approximation of multi-knapsack problems, leading to a regret algorithm that evaluates each scenario with a single mathematical programming optimization followed by a small number of dynamic programs for one-dimensional knapsacks. It also proposes several integer programming models for handling cancellations and proves their equivalence. On the experimental side, the paper demonstrates the effectiveness of the regret algorithm on multi-knapsack problems (with and without overbooking) based on the benchmarks proposed earlier.

Reviews

Required fields are marked *. Your email address will not be published.