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

Vol 56, 2024 - 310142
Complete Articles (CA)
Download
Favorite this paper
How to cite this paper?
Abstract

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.

Questions (1 topic)

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Author

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.

Programme
15:00 to 16:30 on 11/06/2024
Pedro Lazar 1
Institutions
  • 1 Shipping Optimization Team (SOT) - Mercado Libre
Track
  • 12. L&T – Logistics and Transport
Keywords
Knapsack Problem
Exact algorithms
Integer Programming