A Hybrid Matheuristic Applied to the Knapsack Problem with Forfeits
Autores
|
7560 |
539,3267,3266
|
|
|
7561 |
539,3267,3266
|
|
|
7562 |
539,3267,3266
|
Informações:
Publicações do PESC
Esta dissertação de mestrado aborda o Problema da Mochila com Perdas (KPF), uma extensão do clássico Problema da Mochila 0–1 que introduz conflitos suaves entre itens. No KPF, selecionar certos pares de itens juntos incorre em uma penalidade de lucro em vez de ser proibido de imediato. Esse modelo captura melhor cenários do mundo real envolvendo incompatibilidades parciais. A metodologia proposta, chamada Hybrid Data Mining ILS-VND (HDM-ILS-VND), integra uma Busca Local Iterada com Descida de Vizinhança Variável (ILS-VND) com dois aprimoramentos principais: mineração frequente de conjuntos de itens e ramificação local. Na fase de mineração de dados, padrões são descobertos a partir de um conjunto de soluções de elite, orientando a construção de um modelo linear misto-inteiro cuja região viável é restrita a combinações promissoras. Uma fase de ramificação local então refina ainda mais a melhor solução encontrada. Experimentos computacionais foram conduzidos em instâncias de referência usadas na literatura. Os resultados confirmam que o HDM-ILS-VND supera a abordagem ILS-VND padrão e rivaliza com métodos de última geração. Em muitos casos, ele encontra melhores soluções, mantendo tempos de computação razoáveis. Uma análise estatística completa por meio de um Teste de Postos Sinalizados de Wilcoxon valida a superioridade da abordagem híbrida proposta. Esta Dissertação destaca a vantagem de aumentar a heurística com insights de mineração de dados e ramificação local para resolver efetivamente o KPF. A estrutura computacional é mostrada muito robusta no geral.
This Master’s Thesis addresses the Knapsack Problem with Forfeits (KPF), an extension of the classic 0–1 Knapsack Problem introducing soft conflicts among items. In KPF, selecting certain item pairs together incurs a profit penalty rather than being forbidden outright. Such a model better captures real-world scenarios involving partial incompatibilities. The proposed methodology, called Hybrid Data Mining ILS-VND (HDM-ILS-VND), integrates an Iterated Local Search with Variable Neighborhood Descent (ILS-VND) with two key enhancements: frequent itemset mining and local branching. In the data mining phase, patterns are discovered from an elite set of solutions, guiding the construction of a mixed-integer linear model whose feasible region is restricted to promising combinations. A local branching phase then further refines the best solution found. Computational experiments were conducted on benchmark instances used in the literature. The results confirm that HDM-ILS-VND outperforms the standard ILS-VND approach and rivals state-of-the-art methods. On many instances, it finds better solutions while maintaining reasonable computation times. A thorough statistical analysis via a Wilcoxon Signed-Rank Test validates the superiority of the proposed hybrid approach. This thesis highlights the advantage of augmenting heuristics with data mining insights and local branching to solve KPF effectively. The computational framework is shown to be very robust overall.