2310. Online Stochastic Generalized Assignment Problem with Delayed Demand Learning
Invited abstract in session MA-38: Automating the Design, Generation and Control of Optimization Algorithms 1, stream Data Science meets Optimization.
Monday, 8:30-10:00Room: Michael Sadler LG19
Authors (first author is the speaker)
| 1. | Hao Wang
|
| 2. | Zihao Li
|
| , | |
| 3. | LIMENG LIU
|
| SPMS, Nanyang Technological University | |
| 4. | Zhenzhen Yan
|
| Nanyang Technological University |
Abstract
We study an online generalized assignment problem under a stochastic arrival model. Items arrive sequentially, following a known independent and identical distribution. Each arriving item has an associated demand, which is stochastic and drawn from an unknown type-specific distribution. However, a key challenge is that the actual demand is only revealed after a delay, occurring some time after the item has been successfully packed into an offline bin. Such delayed demand revelation is common in many real-world applications, such as food delivery, where actual order sizes or customer consumption patterns may only be observed post-allocation.
Upon each item’s arrival, an immediate decision must be made: either pack it into a bin, reducing its capacity, or reject it. The objective is to maximize the total reward of the packing scheme while adhering to capacity constraints. To tackle the uncertainty introduced by delayed demand revelation, we design an algorithm based on the exploration-exploitation principle, which simultaneously learns about the demand distribution and optimally allocates items. We provide a non-asymptotic parametric guarantee for discrete demand distributions supported on finite rational values and extend our analysis to arbitrary distributions. Finally, we conduct numerical experiments to evaluate the effectiveness of our algorithm across different demand distributions.
Keywords
- Algorithms
- Analytics and Data Science
- Revenue Management and Pricing
Status: accepted
Back to the list of papers