Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918050985410560 |
|---|---|
| author | Bui, Quang Minh Carvalho, Margarida Neto, José |
| author_facet | Bui, Quang Minh Carvalho, Margarida Neto, José |
| contents | The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader's goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower's problem as a longest path problem using a dynamic programming model, and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to two distinct dynamic programming models, namely, a novel formulation designated as selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across three different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the two proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_12923 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models Bui, Quang Minh Carvalho, Margarida Neto, José Optimization and Control Discrete Mathematics 90C46, 90C27, 90C39 The combinatorial pricing problem (CPP) is a bilevel problem in which the leader maximizes their revenue by imposing tolls on certain items that they can control. Based on the tolls set by the leader, the follower selects a subset of items corresponding to an optimal solution of a combinatorial optimization problem. To accomplish the leader's goal, the tolls need to be sufficiently low to discourage the follower from choosing the items offered by the competitors. In this paper, we derive a single-level reformulation for the CPP by rewriting the follower's problem as a longest path problem using a dynamic programming model, and then taking its dual and applying strong duality. We proceed to solve the reformulation in a dynamic fashion with a cutting plane method. We apply this methodology to two distinct dynamic programming models, namely, a novel formulation designated as selection diagram and the well-known decision diagram. We also produce numerical results to evaluate their performances across three different specializations of the CPP and a closely related problem that is the knapsack interdiction problem. Our results showcase the potential of the two proposed reformulations over the natural value function approach, expanding the set of tools to solve combinatorial bilevel programs. |
| title | Solving Combinatorial Pricing Problems using Embedded Dynamic Programming Models |
| topic | Optimization and Control Discrete Mathematics 90C46, 90C27, 90C39 |
| url | https://arxiv.org/abs/2403.12923 |