Premium
An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs
Author(s) -
Penuel John,
Smith J. Cole,
Yuan Yang
Publication year - 2010
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20401
Subject(s) - mathematical optimization , facility location problem , benders' decomposition , integer (computer science) , stochastic programming , integer programming , decomposition , computer science , shortest path problem , residual , binary number , stage (stratigraphy) , path (computing) , 1 center problem , mathematics , algorithm , graph , theoretical computer science , biology , programming language , ecology , paleontology , arithmetic
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. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010