Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems

Esra Büyüktahtakın

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

This paper presents strong scenario dominance cuts for effectively solving the multi-stage stochastic mixed-integer programs (M-SMIPs), specifically focusing on the two most well-known M-SMIPs: stochastic capacitated multi-item lot-sizing (S-MCLSP) and the stochastic dynamic multi-dimensional knapsack (S-MKP) problems. Scenario dominance is characterized by a partial ordering of scenarios based on the pairwise comparisons of random variable realizations in a scenario tree of a stochastic program. In this paper, we study the implications of scenario-dominance relations and inferences obtained by solving scenario sub-problems to drive new strong cutting planes to solve S-MCLSP and S-MKP instances faster. Computational experiments demonstrate that our strong scenario dominance cuts can significantly reduce the solution time for such M-SMIP problems with an average of 0.06% deviation from the optimal solution. The results with up to 81 random variables for S-MKP show that strong dominance cuts improve the state-of-the-art solver solution of two hours by 0.13% in five minutes. The proposed framework can also be applied to other scenario-based optimization problems.

Original languageEnglish (US)
Article number106149
JournalComputers and Operations Research
Volume153
DOIs
StatePublished - May 2023
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research

Keywords

  • Bounds
  • Cutting planes
  • Dynamic knapsack problem
  • Inventory-production management
  • Lot-sizing
  • MIP test problem library
  • Multi-stage stochastic mixed-integer programs
  • Partial ordering of scenarios
  • Scenario dominance
  • Scenario tree
  • Stochastic

Fingerprint

Dive into the research topics of 'Scenario-dominance to multi-stage stochastic lot-sizing and knapsack problems'. Together they form a unique fingerprint.

Cite this