The rank pricing problem : a mixed-integer linear optimization approach

Abstract

Esta tesis está dedicada a un estudio en profundidad del Problema de Tarificación basado en Preferencias (del inglés, Rank Pricing Problem (RPP)) y dos generalizaciones. El RPP es un problema de optimización combinatoria que tiene como objetivo fijar el precio de los productos de una compañía para maximizar su beneficio. En él, intervienen clientes unit-demand, es decir, clientes que están interesados en varios de los productos de la empresa, pero pretenden comprar como mucho uno de ellos. Los clientes tienen un presupuesto fijo y clasifican los productos que les interesan formando un ranking del “mejor” al “peor”. Cuando la compañía fije los precios, cada cliente comprará su producto preferido de entre los que se puede permitir. En el RPP, asumimos que los productos se ofertan en cantidad ilimitada, lo cual encaja si consideramos que la compañía tiene suficientes productos para satisfacer la demanda, o cuando los productos se pueden producir rápidamente con un coste despreciable (por ejemplo, los bienes digitales). Esta tesis doctoral consta de cuatro capítulos. El primero de ellos es un capítulo de introducción al problema y a los conceptos matemáticos presentes en la tesis, mientras que los tres siguientes se centran en cada uno de los problemas estudiados: el RPP y dos generalizaciones. Así, el tercer capítulo está dedicado al estudio del Problema de Tarificación basado en Preferencias con Empates (RPPT por sus siglas en inglés, Rank Pricing Problem with Ties). En esta extensión del problema, asumimos que los clientes pueden expresar su indiferencia entre productos de su interés mediante empates en su lista de preferencia. Y el último capítulo de la tesis comprende el estudio del Problema de Tarificación Capacitado basado en Preferencias o Capacitated Rank Pricing Problem (CRPP) con envidia. En esta extensión, hemos asumido precios de reserva en los clientes que reflejan lo que están dispuestos a pagar por cada producto, en vez de un solo presupuesto por consumidor. No obstante, la principal diferencia es que en el CRPP la compañía tiene un número limitado de productos y puede no ser capaz de satisfacer la demanda de todos los clientes. El objetivo de la tesis es obtener formulaciones lineales enteras mixtas para los tres problemas estudiados, y compararlas teórica y/o computacionalmente. Para ello, la metodología empleada se basa en la propuesta de variables de decisión y restricciones apropiadas que modelicen el problema. El siguiente objetivo es la mejora de estas formulaciones mediante desigualdades válidas que reducen la región factible de la relajación del problema y permiten obtener una mejor cota de la relajación lineal. Y finalmente, un tercer objetivo es la propuesta de algoritmos de resolución para cada uno de estos modelos, y su posterior comparativa mediante la realización de estudios computacionales y resolución mediante optimizadores comerciales. En el Capítulo 2 introducimos dos formulaciones no lineales para el RPP, una que surge de una formulación binivel y otra que está formulada directamente en un solo nivel. Las comparamos teóricamente, linealizamos su función objetivo (que es la misma en ambos casos) de dos formas distintas y proponemos técnicas de preprocesamiento que reducen el tamaño de las instancias fijando variables binarias a cero o a uno. También estudiamos el problema de empaquetamiento asociado a las variables binarias del mejor modelo, con lo que probamos que esta formulación es muy fuerte porque la mayoría de las restricciones que contiene definen facetas del subproblema asociado. Los resultados computacionales son consistentes con nuestra comparación teórica, ya que muestran la superioridad del modelo uninivel. También revelan que se obtienen mejores cotas y un mejor rendimiento en general con una de las linealizaciones propuestas, que se emplea en capítulos posteriores. En el Capítulo 3, proponemos la primera formulación con variables de tres índices para el RPPT. Luego incluimos un método de resolución basado en la introducción de un modelo más débil con un conjunto de variables y restricciones de menor tamaño (el modelo de dos índices), formulación que a continuación fortalecemos añadiendo desigualdades válidas. El segundo método de resolución propuesto está basado en la descomposición de Benders, un método ampliamente utilizado para problemas enteros mixtos. Así, proponemos un Modelo de Benders válido con un conjunto de variables y restricciones pequeño, que reforzamos mediante desigualdades válidas que surgen de la resolución de los subproblemas de Benders. En los experimentos computacionales, observamos que cada uno de los algoritmos de resolución propuestos destaca en una fase de la resolución del problema. En la fase de la relajación lineal, resulta más rápida la adición de cortes en el modelo de dos índices, ya que las desigualdades se pueden separar por productos (incluso si se incluyen más cortes). En la fase entera, sin embargo, el Modelo de Benders lleva a cabo la exploración de nodos más rápido que el otro modelo, probablemente debido a su reducido número de variables y restricciones. El Capítulo 4 comienza introduciendo una formulación con variables de tres índices para resolver el CRPP. Al contrario que en los capítulos precedentes, en este se incluyen varios conjuntos de desigualdades válidas para dicha formulación que utilizan las restricciones de capacidad y nuevas variables binarias. Estos conjuntos se utilizan después cuando se proyecta el modelo de tres índices en el modelo de dos índices, por lo que las desigualdades obtenidas son más difíciles de separar porque dependen de seis conjuntos de parámetros. Además de resolver el problema de separación con Xpress, también separamos teóricamente un conjunto de desigualdades que resulta muy efectivo en la práctica, y lo relacionamos con un conjunto de cortes propuesto para el RPP. La combinación de estas desigualdades con las últimas que proponemos da como resultado un algoritmo muy eficiente que reúne las ventajas de ambas: proporciona unas de las mejores cotas de la relajación lineal y las fases de inclusión de cortes en el nodo raíz y de ramificación son muy rápidas

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.