Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

The Rank Pricing Problem with Ties

Concepción Domínguez 1 Martine Labbé 1 Alfredo Marín 2
1 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download
Contributor : Martine Labbé <>
Submitted on : Friday, July 3, 2020 - 4:37:37 PM
Last modification on : Monday, April 26, 2021 - 8:10:01 AM
Long-term archiving on: : Thursday, September 24, 2020 - 8:47:44 AM


Files produced by the author(s)


  • HAL Id : hal-02889288, version 1



Concepción Domínguez, Martine Labbé, Alfredo Marín. The Rank Pricing Problem with Ties. 2020. ⟨hal-02889288⟩



Record views


Files downloads