Industrial and Systems Engineering
University of Florida

EIN 6918: Graduate Seminar
Spring 2008

March 27, 2008

3PM, MAEB 211

An Integer Decomposition Algorithm for Solving a Two-Stage Facility Location

Problem with Second-Stage Activation Costs

John Penuel

Department of Industrial and Systems Engineering

University of Florida

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, while 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.