26 fev 2025
14:00 Defesa de Mestrado Auditório do IC3
Tema
Formulações de Programação Linear Inteira para o Problema da Compra Mínima
Aluno
Sandro Henrique Uliana Catabriga
Orientador / Docente
Rafael Crivellari Saliba Schouery
Breve resumo
Problemas de precificação são problemas dentro da otimização combinatória que envolvem determinar os preços dos produtos de um vendedor de forma que sua receita, decorrente da venda dos itens, seja máxima. Dentre os problemas de precificação existentes, consideramos o Problema da Compra Mínima, em que um vendedor deseja vender um conjunto I de itens para um conjunto B de compradores. Cada comprador b está disposto a pagar até vib pelo item i. O vendedor deve então definir preços pi para cada i ∈ I de forma a maximizar sua receita, considerando que cada comprador b comprará (se existir) o item mais barato dentre aqueles que pi ≤ vib. Neste trabalho, propomos quatro formulações de Programação Linear para o Problema da Compra Mínima, sendo uma de Programação Linear Inteira (PLI) e três de Programação Linear Inteira Mista (PLIM). Exploramos duas formas principais de se resolver o Problema da Compra Mínima, uma determinando os preços dos itens e os preços pagos pelos compradores, para então indiretamente determinar a alocação dos itens aos compradores, e outra determinando a alocação de forma direta. Foram introduzidas desigualdades válidas em 3 modelos para criar modelos fortalecidos, visando reduzir o tempo de execução e aumentar o número de instâncias solucionadas. Um teorema foi apresentado, demonstrando que é suficiente considerar um subconjunto de preços para cada item, correspondendo às valorações oferecidas a ele. Com isso, foi possível reduzir o número de variáveis e restrições dos modelos. Avaliamos as formulações utilizando três classes de instâncias esparsas, Characteristics, Neighborhood e Popularity, que simulam diferentes cenários práticos de preferências de consumidores, e também instâncias densas, ou completas, onde todo comprador oferece uma valoração para todo item. Os experimentos mostraram que as desigualdades válidas melhoraram os resultados de 2 modelos. O modelo de PLI fortalecido obteve o melhor resultado para instâncias esparsas, enquanto que um modelo de PLIM obteve o melhor resultado para instâncias densas. Um dos modelos de PLIM obteve o melhor equilíbrio dentre todos os modelos, destacando-se como o melhor modelo de PLIM para instâncias esparsas e resolvendo todas as instâncias densas em um bom tempo.
Banca examinadora
Titulares:
Rafael Crivellari Saliba Schouery IC/UNICAMP
Ruben Interian Kovaliova IC/UNICAMP
Mauro Henrique Mulati DIN/UEM
Suplentes:
Santiago Valdés Ravelo IC/UNICAMP
Pedro Henrique Del Bianco Hokama IMC/UNIFEI