The Path-Precedence Constrained Knapsack Problem with Unit Weights: Exact Algorithms, Linear Formulations and Instances

Vol 56, 2024 - 310142
Trabalho completo (Oral)
Download
Favoritar este trabalho
Como citar esse trabalho?
Resumo

This work formalizes a special case of the strongly NP-Hard problem Precedence Constrained Knapsack Problem (PCKP). In this special case, the precedence constraints are restricted to paths within the same class of items, and all items have weight equal to one. This special case is named as Path-Precedence Constrained Knapsack Problem with Unit Weights (PPCKP-UW) and it has real-world applications, including a demand in logistics for solving it in real-time. This work proves that PPCKP-UW is solvable in polynomial-time, compares the computational performance of solving it using seven different approaches, including integer linear formulations, algorithms based on dynamic programming and shortest path, and applying pre/post-processing tasks to the instances. Ten new instances were generated and shared with the source codes, allowing the reproduction of all experiments made. Experimental results showed that the proposed approaches run faster than the conventional formulation based on PCKP.

Questões (1 tópico)

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Autor

Cristiano Martins Monteiro

Boa tarde!

Obrigado pelos comentários e pelas perguntas!

Respondendo:

  • É horizonte rolante ou problema é definitivo de forma estática?
    • O problema é definido de forma estática.
       
  • Já pensaram em trabalhar o problema com incertezas?
    • No nosso caso não se aplica, porque já temos certeza sobre todos os itens que fazem parte da instância. O problema está somente em quais itens serão colocados na mochila.
       
  • Já pensaram em utilizar aproximação de programação dinâmica para definir políticas sub-ótimas?
    • Não pensamos em usar outros métodos porque os algoritmos atuais são o suficiente para encontrar o ótimo global e rodam dentro do tempo limite para processamento. Mas de fato isso pode mudar no futuro caso as instâncias fiquem maiores, ou o tempo limite de processamento reduza.
    • De qualquer forma, é um tema interessante para a comunidade científica avançar.

As implementações e instâncias do artigo estão disponíveis abertamente caso alguém tenha interesse em seguir a pesquisa. O link para download e definição dos algoritmos propostos estão descritos no corpo do artigo.

Programação
15:00 até 16:30 em 06/11/2024
Pedro Lazar 1
Instituições
  • 1 Shipping Optimization Team (SOT) - Mercado Libre
Eixo Temático
  • 12. L&T – Logística e Transportes
Palavras-chave
Knapsack Problem
Exact algorithms
Integer Programming