  Promotions and discounts are essential components of modern e-commerce
platforms, where they are often used to incentivize customers towards purchase
completion. Promotions also affect revenue and may incur a monetary loss that
is often limited by a dedicated promotional budget. We study the Online
Constrained Multiple-Choice Promotions Personalization Problem, where the
optimization goal is to select for each customer which promotion to present in
order to maximize purchase completions, while also complying with global budget
limitations. Our work formalizes the problem as an Online Multiple Choice
Knapsack Problem and extends the existent literature by addressing cases with
negative weights and values. We provide a real-time adaptive method that
guarantees budget constraints compliance and achieves above 99.7% of the
optimal promotional impact on various datasets. Our method is evaluated on a
large-scale experimental study at one of the leading online travel platforms in
the world.
