The rank pricing problema mixed-integer linear optimization approach

Abstract

This doctorate is entirely devoted to an in-depth study of the Rank Pricing Problem (RPP) and two generalizations. The RPP is a combinatorial optimization problem which aims at setting the prices of a series of products of a company to maximize its revenue. This problem is specified by a set of unit-demand customers, that is, customers interested in a subset of the products offered by the company which intend to buy at most one of them. To do so, they count on a fixed budget, and they rank the products of their interest from the “best” to the “worst”. Once the prices are established by the company, they will purchase their highest-ranked product among the ones they can afford. In the RPP, it is assumed an unlimited supply of products, which is consistent with a company having enough copies of a product to satisfy the demand, or with a setting where the products can be produced quickly at negligible cost (e.g., digital goods). This dissertation consists of four chapters. The first chapter introduces the RPP problem and the mathematical concepts present in the work, whereas each of the next three chapters tackles the resolution of each of the problems of study: the RPP and two generalizations. Thus, Chapter 3 is dedicated to the Rank Pricing Problem with Ties (RPPT), an extension of the RPP where we consider that customers can express indifference among products in their preference list. And the last chapter of the thesis is devoted to a generalization of the problem that we have named the Capacitated Rank Pricing Problem (CRPP) with envy. For this generalization, we have considered reservation prices of customers for the different products that reflect their willingness to pay, instead of a single budget per customer. However, the main difference is that, in the CRPP, the company has a limited supply of products and might not be able to satisfy all the customers’ requests. This is a realistic assumption that we can find in many companies. The aim of this thesis is the proposal of mixed-integer linear formulations for the three problems of study, and their theoretical and/or computational comparison. The methodology used is based on the introduction of decision variables and adequate restrictions to model the problems. Another objective consists in strengthening the formulations by means of valid inequalities that reduce the feasible region of the relaxed problem and allow us to obtain better linear relaxation bounds. Finally, a third goal is to derive resolution algorithms for each of these models and compare them computationally, using commercial solvers. In Chapter 2, we give two nonlinear formulations for the RPP, one that comes from a bilevel formulation and another one that is directly formulated as a single-level one. We compare them theoretically, linearize their objective functions (which are the same) in two different ways and propose preprocessing techniques that effectively reduce the size of the instances by fixing variables to either zero or one. By studying the Set Packing Problem associated to the binary variables of the strongest model, we prove that this formulation is very tight, since most of its constraints are facet-defining in the corresponding subproblem. The computational results are consistent with our theoretical comparison, given that they show the superiority of the single-level model. They also disclose that one of the linearizations (used in following chapters) outperforms the other. In Chapter 3, we propose the first formulation with three-index variables for the RPPT. Next, we propose a resolution method based on the introduction of a weaker model with much less variables and constraints (the two-index model) and its strengthening by means of valid inequalities. The second resolution method is based on the Benders decomposition, a widely used approach for solving mixed-integer programs. Thus, we introduce a valid Benders Model with a small number of variables and constraints. Next, we reinforce the model dynamically adding valid inequalities obtained solving the Benders subproblems. In the computational testing, each of the resolution algorithms proposed excels in a specific phase. In the linear relaxation phase, the separation procedure designed to add valid inequalities is faster for the two-index model, since these inequalities can be separated by products. In the integer phase, however, the Benders Model outperforms the two-index model in the tree search because the node exploration is faster, probably due to the small number of variables and constraints it has. Chapter 4 begins with the introduction of a model with three-index variables for the CRPP. Unlike in the previous chapters, here the capacity constraints and the inclusion of new variables associated to the capacity allow to derive several sets of valid inequalities for the three-index formulation. These sets are then included in the projection of the three-index formulation into the two-index one, so the resultant inequalities are more difficult to separate because they depend on six sets of parameters. Besides solving the separation problem with Xpress, we theoretically separate a particular set of inequalities that proves to be very effective in practice, and link it with a family proposed for the RPP. The combination of these inequalities with the last set proposed results in a very efficient resolution method that combines the best linear relaxation gap with a rather quick inclusion of cuts in the root node and an effective node search.