Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem

D.D. Tönissen, J.M. van den Akker, J.A. Hoogeveen

Research output: Contribution to journalArticleAcademicpeer-review

4 Citations (Scopus)
3 Downloads (Pure)

Abstract

Many problems can be formulated by variants of knapsack problems. However, such models are deterministic, while many real-life problems include some kind of uncertainty. Therefore, it is worthwhile to develop and test knapsack models that can deal with disturbances. In this paper, we consider a two-stage stochastic multiple knapsack problem. Here, we have a multiple knapsack problem together with a set of possible disturbances. For each disturbance, or scenario, we know its probability of occurrence and the resulting reduction in the sizes of the knapsacks. For each knapsack we decide in the first stage which items we take with us, and when a disturbance occurs we are allowed to remove items from the corresponding knapsack. Our goal is to find a solution where the expected revenue is maximized. We use branch-and-price to solve this problem. We present and compare two solution approaches: the separate recovery decomposition (SRD) and the combined recovery decomposition (CRD). We prove that the LP-relaxation of the CRD is stronger than the LP-relaxation of the SRD. Furthermore, we investigate numerous column generation strategies and methods to create additional columns outside the pricing problem. These strategies reduce the solution time significantly. To the best of our knowledge, there is no other paper that investigates such strategies so thoroughly.

Original languageEnglish
Pages (from-to)125-139
Number of pages15
JournalComputers & Operations Research
Volume83
DOIs
Publication statusPublished - 1 Jul 2017

Keywords

  • Branch-and-price
  • Column generation
  • Multiple knapsack problem
  • Recoverable robustness
  • Two-stage stochastic programming

Fingerprint Dive into the research topics of 'Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem'. Together they form a unique fingerprint.

Cite this