Models and algorithms for the product pricing with single-minded customers requesting bundles

• Published in: Computers & operations research 2021-03, Vol.127, p.105139, Article 105139
• Main Authors: Bucarey, Víctor, Elloumi, Sourour, Labbé, Martine, Plein, Fränk
• Format: Article
• Language: English
• Subjects: Algorithms; Benders decomposition; Computer Science; Customers; Discrete Mathematics; Heuristics; Integer programming formulations; Linearization; Mixed integer; Operations Research; Pricing; Pricing problems; Quality assessment
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2020.105139

We analyze a product pricing problem with single-minded customers, each interested in buying a bundle of products, if the total price is less than or equal to their budget. The objective of the seller is to maximize the total revenue and we assume that supply is unlimited for all products. We contribute to a missing piece of literature by giving some mathematical formulations for this single-minded bundle pricing problem. We first present a mixed-integer nonlinear program with bilinear terms in the objective function and the constraints. By applying classical linearization techniques, we obtain two different mixed-integer linear reformulations. Inspired by a reformulation–linearization technique framework, we derive valid inequalities leading to a tighter linear reformulation. We then discuss a Benders decomposition to project strong cuts from the tightest model onto a light and fast model. In another attempt to exploit the tighter linear relaxation, we discuss heuristics based on the developed mixed-integer linear formulations to quickly find good solutions. We conclude this work with extensive numerical experiments to assess the quality of the mixed-integer linear formulations, as well as the performance of the Benders decomposition and the heuristics.