The Rank Pricing Problem with Ties
Document type :
Compte-rendu et recension critique d'ouvrage
Title :
The Rank Pricing Problem with Ties
Author(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
Journal title :
European Journal of Operational Research
Publisher :
Elsevier
Publication date :
2021
ISSN :
0377-2217
English keyword(s) :
Combinatorial Optimization
Pricing Problems
Integer Programming
Bilevel Programming
Benders Decomposition
Pricing Problems
Integer Programming
Bilevel Programming
Benders Decomposition
HAL domain(s) :
Computer Science [cs]/Operations Research [math.OC]
English abstract : [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, ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Popular science :
Non
Collections :
Source :
Files
- https://hal.inria.fr/hal-02889288/document
- Open access
- Access the document
- https://hal.inria.fr/hal-02889288/document
- Open access
- Access the document
- https://hal.inria.fr/hal-02889288/document
- Open access
- Access the document
- document
- Open access
- Access the document
- RPPT-final.pdf
- Open access
- Access the document