The rank pricing problema mixed-integer linear optimization approach

Resumen

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