stochastic knapsack

Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Alejandro Toriello
    • Categories Combinatorial Optimization, Dynamic Programming Tags ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can dynamically choose the next item based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

    Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes

  • Daniel Blado
  • Weihong Hu
  • Alejandro Toriello
    • Categories 0-1 Programming, Dynamic Programming Tags , ,

    We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more