Facility Location Under Uncertainty - Location Science - page 193

for minmax problems (e.g., Mausser and Laguna ( 1998 ), for minmax regret linear
problems with interval uncertainty) in most cases, specially tailored procedures,
exact or approximate, must be developed for efficiently tackling the problems.
Analytic results and polynomial time algorithms have also been proposed but only
for problems with some underlying structure, such as a network.
As far as stochastic discrete facility location problems are concerned, again, they
are often difficult to solve to optimality. Even when the number of scenarios is finite
and an extensive form of the deterministic equivalent can be obtained, we often end
up with a large-scale mixed-integer linear programming problem not manageable
by a general solver. In this case, specific approaches, exact or heuristic, have to be
developed for tackling the problems. Laporte et al. ( 1994 )makeuseoftheinteger
L-shaped method proposed by Laporte and Louveaux ( 1993 ) for solving a two-stage
stochastic facility location problem with first-stage binary variables. In the context
of logistics systems, Alonso-Ayuso et al. ( 2003 ) introduce the so-called branch-
and-fix coordination scheme, which they consider for solving a stochastic facility
location problem. The technique proposed can be used for solving general two-stage
stochastic programming problems with binary first-stage variables and both binary
and continuous variables in the second stage.
A general approach for multi-stage stochastic mixed-integer linear programming
problems was proposed by Escudero et al. ( 2009 , 2010 ). In those papers, the branch-
and-fix coordination scheme proposed by Alonso-Ayuso et al. ( 2003 ) was extended
in order to solve multi-stage problems with integer variables. As mentioned above,
Hernández et al. ( 2012 ) embed such approach within a heuristic procedure.
When exact approaches fail to solve the problems, we must resort to approximate
procedures. One particular difficulty in stochastic programming arises when the
number of scenarios is too large or even infinite. In this case, one possibility is
to use a sampling approach. The sample average approximation approach (SAA)
introduced by Kleywegt et al. ( 2001 ) is one such example which has become
quite popular. Applications of this approach to stochastic facility location were
proposed by Kiya and Davoudpour ( 2012 ), Romauch and Hartl ( 2005 ) and Santoso
et al. ( 2005 ). Sampling approaches have also been proposed for general chance-
constrained problems by Luedtke and Ahmed ( 2008 ) and Pagnoncelli et al. ( 2009 ).
The application to facility location problems is still to be explored.
Other algorithms for stochastic programming problems include the generation
of cutting planes introduced by Guan et al. ( 2009 ) for multi-stage problems, and
the dual decomposition based approaches developed by Carrøe and Schultz ( 1999 )
and Escudero et al. ( 2012 ). To the best of our knowledge, the first type of approach
was never applied to stochastic facility location. However, there are several papers
proposing dual decomposition based algorithms for problems that include location
decisions, namely those by Schütz et al. ( 2008 , 2009 ). The latter work combines dual
decomposition with SAA. In this type of method, the non-anticipativity constraints
are explicitly considered in the model and dualized, which allows a scenario-
decoupling for the relaxed problem.