O método de trajetória dual para fixação de variáveis com aplicação ao problema de recobrimento de conjuntos

Yamagishi, Paulo Michel Fajardo

Please use this identifier to cite or link to this item:


			http://hdl.handle.net/11422/29000

Type:	Trabalho de conclusão de graduação
Title:	O método de trajetória dual para fixação de variáveis com aplicação ao problema de recobrimento de conjuntos
Author(s)/Inventor(s):	Yamagishi, Paulo Michel Fajardo
Advisor:	Coutinho, Severino Collier
Co-advisor:	Fampa, Márcia Helena Costa
Abstract:	Este trabalho propõe o Dual Path Fixing (DPF), técnica de fixação de variáveis para o Problema de Cobertura de Conjuntos que explora soluções duais intermediárias geradas durante o algoritmo Simplex. O método clássico de reduced cost fixing (RCF) utiliza apenas a solução dual ótima da relaxação linear, descartando informações valiosas produzidas ao longo da execução. A inovação metodológica do DPF consiste na utilização de um algoritmo dual viável para resolver a relaxação contínua do SCP ou, equivalentemente, de um algoritmo primal viável para resolver o dual da relaxação, de forma a obter uma solução viável para o problema dual a cada iteração do algoritmo. Essa abordagem garante que todas as soluções intermediárias sejam duais factíveis, habilitando a aplicação do critério de fixação em cada iteração sem custo computacional adicional significativo. Para viabilizar a coleta dessas soluções, o trabalho adapta o solver GLPK 5.0, modificando seu código-fonte para extrair vetores duais durante a execução do Simplex. A validação experimental compreende 60 instâncias: 25 derivadas de Safety Landing Sites (até 2500 variáveis e 35000 restrições) e 35 do benchmark OR-Library (até 4000 variáveis). Nas instâncias SLS, o DPF fixa consistentemente mais variáveis que o RCF (incremento médio de 2%), identificando 63% das variáveis como fixáveis em zero. Nas instâncias OR-Library, alcança taxa de fixação média de 91,5%, superando o RCF em 0,2 pontos percentuais. A análise temporal demonstra que aproximadamente 60% das fixações ocorrem com 60% das iterações do Simplex nas instâncias SLS, enquanto nas instâncias OR-Library esse percentual atinge 70–80% até 50% das iterações. Ademais, o trabalho desenvolve extensões iterativas que alternam fixação de variáveis com eliminação de linhas dominadas (DRE), explorando a sinergia entre as técnicas. Os métodos iterativos alcançam 69,8% de redução (I(DPF)) versus 67,3% (I(RCF)) nas instâncias SLS, e 91,8% versus 91,5% nas instâncias OR-Library. A comparação com strong fixing estabelece que o DPF alcança 79,6% da eficácia desta técnica nas instâncias SLS (69,8% versus 87,7%) e 98% nas instâncias OR-Library (91,8% versus 93,8%) com custo computacional ordens de grandeza menor, posicionando-se como alternativa com melhor trade-off para problemas de grande porte.
Keywords:	Problema de cobertura de conjuntos Programação inteira Soluções duais Relaxação linear Algoritmo Simplex Set covering problem Integer programming Dual solutions Linear relaxation Simplex algorithm Reduced cost fixing
Subject CNPq:	CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Production unit:	Instituto de Computação
Publisher:	Universidade Federal do Rio de Janeiro
Issue Date:	10-Feb-2026
Publisher country:	Brasil
Language:	por
Right access:	Acesso Aberto
Appears in Collections:	Ciência da Computação

Files in This Item:

File	Description	Size	Format
PMFYamagishi.pdf		448.57 kB	Adobe PDF	View/Open ???org.dspace.app.webui.jsptag.ItemTag.restrict???

Show full item record Recommend this item View Statistics

Pantheon Institutional repository