The Rank Pricing Problem with Ties
Type de document :
Compte-rendu et recension critique d'ouvrage
Titre :
The Rank Pricing Problem with Ties
Auteur(s) :
Domínguez, Concepción [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Marín, Alfredo [Auteur]
Departamento de Estadística e Investigación Operativa, Facultad de Matematicas
Integrated Optimization with Complex Structure [INOCS]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Marín, Alfredo [Auteur]
Departamento de Estadística e Investigación Operativa, Facultad de Matematicas
Titre de la revue :
European Journal of Operational Research
Éditeur :
Elsevier
Date de publication :
2021
ISSN :
0377-2217
Mot(s)-clé(s) en anglais :
Combinatorial Optimization
Pricing Problems
Integer Programming
Bilevel Programming
Benders Decomposition
Pricing Problems
Integer Programming
Bilevel Programming
Benders Decomposition
Discipline(s) HAL :
Computer Science [cs]/Operations Research [math.OC]
Résumé en anglais : [en]
In the Rank Pricing Problem (RPP), a firm intends to maximize its profit through the pricing of a set of products to sell. Customers are interested in purchasing at most one product among a subset of products. To do so, ...
Lire la suite >In the Rank Pricing Problem (RPP), a firm intends to maximize its profit through the pricing of a set of products to sell. Customers are interested in purchasing at most one product among a subset of products. To do so, they are endowed with a ranked list of preferences and a budget. Their choice rule consists in purchasing the highest-ranked product in their list and whose price is below their budget. In this paper, we consider an extension of RPP, the Rank Pricing Problem with Ties (RPPT), in which we allow for indifference between products in the list of preferences of the customers. Considering the bilevel structure of the problem, this generalization differs from the RPP in that it can lead to multiple optimal solutions for the second level problems associated to the customers. In such cases, we look for pessimistic optimal solutions of the bilevel problem : the customer selects the cheapest product. We present a new three-indexed integer formulation for RPPT and introduce two resolution approaches. In the first one, we project out the customer decision variables, obtaining a reduced formulation that we then strengthen with valid inequalities from the former formulation. Alternatively, we follow a Benders decomposition approach leveraging the separability of the problem into a master problem and several subproblems. The separation problems to include the valid inequalities to the master problem dynamically are shown to reduce to min-cost flow problems. We finally carry out extensive computational experiments to assess the performance of the resolution approaches.Lire moins >
Lire la suite >In the Rank Pricing Problem (RPP), a firm intends to maximize its profit through the pricing of a set of products to sell. Customers are interested in purchasing at most one product among a subset of products. To do so, they are endowed with a ranked list of preferences and a budget. Their choice rule consists in purchasing the highest-ranked product in their list and whose price is below their budget. In this paper, we consider an extension of RPP, the Rank Pricing Problem with Ties (RPPT), in which we allow for indifference between products in the list of preferences of the customers. Considering the bilevel structure of the problem, this generalization differs from the RPP in that it can lead to multiple optimal solutions for the second level problems associated to the customers. In such cases, we look for pessimistic optimal solutions of the bilevel problem : the customer selects the cheapest product. We present a new three-indexed integer formulation for RPPT and introduce two resolution approaches. In the first one, we project out the customer decision variables, obtaining a reduced formulation that we then strengthen with valid inequalities from the former formulation. Alternatively, we follow a Benders decomposition approach leveraging the separability of the problem into a master problem and several subproblems. The separation problems to include the valid inequalities to the master problem dynamically are shown to reduce to min-cost flow problems. We finally carry out extensive computational experiments to assess the performance of the resolution approaches.Lire moins >
Langue :
Anglais
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-02889288/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-02889288/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-02889288/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- RPPT-final.pdf
- Accès libre
- Accéder au document