Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.18653 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918397188505600 |
|---|---|
| author | Shao, Zi Yuan Eric |
| author_facet | Shao, Zi Yuan Eric |
| contents | We study a discrete portfolio pricing problem that selects one price per product from a finite menu under margin and fairness constraints. To account for demand uncertainty, we incorporate a budgeted robust formulation that controls conservatism while remaining computationally tractable. By reducing the problem to a Multiple-Choice Knapsack Problem (MCKP), we identify structural properties of the LP relaxation, in particular upper-hull filtering and greedy filling over hull segments, that yield an exact solution method for the LP relaxation of the fixed-parameter subproblems. For the resulting fixed-parameter subproblems, we show that the integrality gap is bounded additively by a single-item hull jump, and that the corresponding relative gap decays as O(1/n) under standard boundedness and linear-growth assumptions. Numerical experiments on synthetic portfolios and a stylized retail case study with economically calibrated parameters are consistent with these bounds and indicate that robust margin protection can be achieved with less than 1 percent nominal revenue loss on the instances tested. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18653 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Robust Discrete Pricing Optimization via Multiple-Choice Knapsack Reductions Shao, Zi Yuan Eric Optimization and Control We study a discrete portfolio pricing problem that selects one price per product from a finite menu under margin and fairness constraints. To account for demand uncertainty, we incorporate a budgeted robust formulation that controls conservatism while remaining computationally tractable. By reducing the problem to a Multiple-Choice Knapsack Problem (MCKP), we identify structural properties of the LP relaxation, in particular upper-hull filtering and greedy filling over hull segments, that yield an exact solution method for the LP relaxation of the fixed-parameter subproblems. For the resulting fixed-parameter subproblems, we show that the integrality gap is bounded additively by a single-item hull jump, and that the corresponding relative gap decays as O(1/n) under standard boundedness and linear-growth assumptions. Numerical experiments on synthetic portfolios and a stylized retail case study with economically calibrated parameters are consistent with these bounds and indicate that robust margin protection can be achieved with less than 1 percent nominal revenue loss on the instances tested. |
| title | Robust Discrete Pricing Optimization via Multiple-Choice Knapsack Reductions |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2603.18653 |