An integer decomposition algorithm for solving a two-stage facility location problem with second-stage activation costs

John Penuel, J. Cole Smith, Yang Yuan

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

We study a stochastic scenario-based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first-stage variables in our problem are the traditional binary facility-location variables, whereas the second-stage variables involve a mix of binary facility-activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second-stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two-stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems.

Original languageEnglish (US)
Pages (from-to)391-402
Number of pages12
JournalNaval Research Logistics
Volume57
Issue number5
DOIs
StatePublished - Aug 1 2010
Externally publishedYes

Keywords

  • Cutting planes
  • Decomposition
  • Facility location
  • Stochastic integer programming

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'An integer decomposition algorithm for solving a two-stage facility location problem with second-stage activation costs'. Together they form a unique fingerprint.

  • Cite this