El Problema de Tarificación basado en Preferencias: Un enfoque desde la optimización lineal entera mixta

Concepción Domínguez
Departamento de Matemática Aplicada. Universidad de Málaga
ORCid: 0000-0002-9046-4997
concepcion.dominguez@uma.es

Directores:
Martine Labbé (Université Libre de Bruxelles)
Alfredo Marín (Universidad de Murcia)
Bernard Fortz (Université Libre de Bruxelles)

Keywords: Optimizacion Combinatoria, Rank Pricing Problem, Optimización Binivel, Descomposición de Benders, Desigualdades Válidas, Problemas de Empaquetamiento.

MSC Subject classifications: 90C11, 90C27, 90B99.

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, empleando herramientas y técnicas propias de la Optimización Matemática. A continuación, se hace una breve descripción de este problema y de las metodologías propuestas para su análisis y resolución.

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 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).

Dentro de la Optimización Matemática, nosotros hemos centrado nuestro trabajo en el desarrollo de métodos exactos para el problema. En concreto, nos centramos en dar formulaciones enteras-mixtas, linealizarlas y/o reforzarlas si corresponde, y desarrollar algoritmos de resolución basados en dichas formulaciones que proporcionan una solución óptima.

Esta tesis 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.

El segundo capítulo se centra en el estudio del RPP. En primer lugar, explicamos que el problema puede ser visto como un problema binivel: la compañía actúa como primer nivel (o líder) maximizando su beneficio; y el segundo nivel lo componen los clientes o seguidores que, de forma independiente, buscan maximizar sus preferencias. Por esto, la primera formulación que presentamos es una formulación binivel que transformamos en una formulación de un nivel utilizando resultados de programación lineal. A continuación, proponemos otra formulación, esta vez directamente en un nivel. Como la función objetivo de ambas formulaciones (que es la misma) es no lineal, introducimos dos linealizaciones a través de dos conjuntos distintos de variables continuas. Así, obtenemos cuatro modelos lineales enteros-mixtos. Después nos centramos en reforzar las cotas superiores dadas por la relajación lineal de los modelos. Para ello presentamos dos conjuntos de desigualdades válidas con número exponencial de desigualdades, y diseñamos algoritmos de separación que determinan cuáles son las más violadas por la solución óptima de la relajación. Nuestro método resulta ser muy eficiente en la separación de las desigualdades, lo que deriva en grandes mejoras de las cotas superiores. Tras la separación, añadimos las desigualdades válidas a la formulación dinámicamente, mediante un procedimiento de ramificación y cortes. Para finalizar, incluimos un apartado con técnicas de preprocesamiento que reducen el tamaño de las instancias del problema, y comparamos las formulaciones y los algoritmos teórica y computacionalmente. Adicionalmente, incluimos un análisis poliédrico de un subproblema de empaquetamiento de conjuntos, en el que identificamos el grafo intersección asociado a nuestro subproblema, y damos una caracterización de todos sus cliques, agrupándolos en dos familias y definiéndolos además mediante una expresión parametrizada común. Los resultados del estudio del RPP se encuentran publicados en Calvete et al. (2019).

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 preferencias.

En este capítulo presentamos una nueva formulación con variables de tres índices e introducimos dos métodos de resolución. En el primero, comenzamos proponiendo una formulación con variables de dos índices, para luego proyectar la anterior en esta, obteniendo un conjunto exponencial de desigualdades válidas que la refuerzan. La matriz asociada a las restricciones de los problemas de separación de dichas desigualdades posee la propiedad de los unos consecutivos, lo que nos permite reducir nuestros problemas de separación a problemas de flujo a coste mínimo y resolverlos mediante un algoritmo existente. Alternativamente, resolvemos la formulación de tres índices siguiendo un esquema basado en la descomposición de Benders que aprovecha la separabilidad del problema en un problema master y varios subproblemas. Además, conseguimos identificar un subconjunto pequeño (polinómico) de restricciones de los subproblemas que nos permiten obtener una formulación master reducida válida para el RPPT, el Modelo de Benders. Finalmente, llevamos a cabo experimentos computacionales exhaustivos para evaluar la efectividad de los métodos de resolución. Los resultados expuestos en el capítulo se encuentran publicados en Dominguez, Labbé, and Marín (2021).

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, la compañía tiene un número limitado de productos y puede no ser capaz de satisfacer la demanda de todos los clientes. Esta es una hipótesis realista que se da, por ejemplo, en compañías que venden productos hechos a mano, en la industria del lujo o en compañías que venden bienes no materiales (experiencias, servicios, entradas para eventos, etc.). En esta extensión, consideramos que las preferencias de los clientes solo se respetan si el producto no se agota en la solución final, es decir, soluciones con envidia.

Comenzamos nuestro estudio analizando la complejidad del subproblema dado por la asignación de los productos a los clientes (asumiendo una tarificación fija), demostrando así que es NP-completo en el caso con envidia. Después, introducimos dos formulaciones lineales enteras mixtas con distintos conjuntos de variables de decisión. Para estas formulaciones, damos tres conjuntos de desigualdades válidas, algunos basados en las restricciones de capacidad, y otros proyectando una formulación en la otra mediante el Lema de Farkas. Finalmente, comparamos los algoritmos desarrollados en el estudio computacional, donde se muestra que las desigualdades válidas propuestas tienen un impacto directo tanto en el tiempo de resolución de ambos modelos como en la reducción de la cota de la relajación lineal. Este trabajo se encuentra publicado en Domínguez, Labbé, and Marín (2022).

La tesis doctoral finaliza con las conclusiones de la investigación realizada y la presentación de líneas de trabajo futuras.
Esta tesis doctoral se ha desarrollado en un programa de cotutela entre la Universidad de Murcia y la Université Libre de Bruxelles.

Agradecimientos

Esta investigación se ha financiado con los proyectos: MTM2015-65915-R (MINECO, Spain), PID2019-110886RB-I00 (MICINN, Spain), PDR T0098.18 (Fonds de la Recherche Scientifique -FNRS), FRIA grant para la realización de un doctorado (Fonds de la Recherche Scientifique – FNRS).

Aceca de la autora

Referencias