Discreteness to Convexity: Promotion Planning via Simplotope Triangulation
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912852830322688 |
|---|---|
| author | He, Taotao Tawarmalani, Mohit |
| author_facet | He, Taotao Tawarmalani, Mohit |
| contents | Price promotion optimization is a computationally challenging problem central to supermarket operations, requiring simultaneous pricing decisions across multiple products and periods. This paper introduces a novel formulation for supermodular functions and univariate compositions using explicit convex hull descriptions derived from simplotope triangulations, departing from prior reliance on rectangular domains. Leveraging this reformulation with Gurobi, we achieve substantial performance gains, with average solve times for problems with 10 products and 5 price levels reducing from 434 to 0.06 seconds, enabling significant instance scaling. We demonstrate conditions for a tight linear programming relaxation extending previous results from two to multiple price levels and from additive to multiplicative historical effects. Our approach is broadly applicable to nonlinear discrete optimization, and we contribute techniques for convexifying compositions of arbitrary univariate functions and a framework for convexifying a superclass of L natural functions, providing powerful tools for revenue management. This work advances the tractability of price promotion optimization, offering a practical and theoretically grounded solution for large-scale supermarket operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_04562 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Discreteness to Convexity: Promotion Planning via Simplotope Triangulation He, Taotao Tawarmalani, Mohit Optimization and Control Price promotion optimization is a computationally challenging problem central to supermarket operations, requiring simultaneous pricing decisions across multiple products and periods. This paper introduces a novel formulation for supermodular functions and univariate compositions using explicit convex hull descriptions derived from simplotope triangulations, departing from prior reliance on rectangular domains. Leveraging this reformulation with Gurobi, we achieve substantial performance gains, with average solve times for problems with 10 products and 5 price levels reducing from 434 to 0.06 seconds, enabling significant instance scaling. We demonstrate conditions for a tight linear programming relaxation extending previous results from two to multiple price levels and from additive to multiplicative historical effects. Our approach is broadly applicable to nonlinear discrete optimization, and we contribute techniques for convexifying compositions of arbitrary univariate functions and a framework for convexifying a superclass of L natural functions, providing powerful tools for revenue management. This work advances the tractability of price promotion optimization, offering a practical and theoretically grounded solution for large-scale supermarket operations. |
| title | Discreteness to Convexity: Promotion Planning via Simplotope Triangulation |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2408.04562 |