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

Fingerprint

Column Generation
Knapsack
Knapsack Problem
Recovery
Disturbance
Decomposition
LP Relaxation
Decompose
Branch-and-price
Pricing
Uncertainty
Scenarios
Strategy
Knapsack problem
Column generation
Model
Costs

Keywords

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

Cite this

@article{c4e630777d7b48f0b4a151d4960e06c9,
title = "Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem",
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.",
keywords = "Branch-and-price, Column generation, Multiple knapsack problem, Recoverable robustness, Two-stage stochastic programming",
author = "D.D. T{\"o}nissen and {van den Akker}, J.M. and J.A. Hoogeveen",
year = "2017",
month = "7",
day = "1",
doi = "10.1016/j.cor.2017.02.009",
language = "English",
volume = "83",
pages = "125--139",
journal = "Computers & Operations Research",
issn = "0305-0548",
publisher = "Elsevier",

}

Column generation strategies and decomposition approaches for the two-stage stochastic multiple knapsack problem. / Tönissen, D.D.; van den Akker, J.M.; Hoogeveen, J.A.

In: Computers & Operations Research, Vol. 83, 01.07.2017, p. 125-139.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Tönissen, D.D.

AU - van den Akker, J.M.

AU - Hoogeveen, J.A.

PY - 2017/7/1

Y1 - 2017/7/1

N2 - 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.

AB - 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.

KW - Branch-and-price

KW - Column generation

KW - Multiple knapsack problem

KW - Recoverable robustness

KW - Two-stage stochastic programming

UR - http://www.scopus.com/inward/record.url?scp=85013339686&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2017.02.009

DO - 10.1016/j.cor.2017.02.009

M3 - Article

AN - SCOPUS:85013339686

VL - 83

SP - 125

EP - 139

JO - Computers & Operations Research

JF - Computers & Operations Research

SN - 0305-0548

ER -