EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

2894. Stochastic facility location problem with outsourcing costs

Invited abstract in session TD-29: Exact Algorithms and Formulations for Combinatorial Optimization Problems, stream Combinatorial Optimization.

Tuesday, 14:30-16:00
Room: 157 (building: 208)

Authors (first author is the speaker)

1. Eduardo Moreno
Faculty of Engineering and Sciences, Universidad Adolfo IbaƱez
2. Ivana Ljubic
IDS, ESSEC Business School of Paris

Abstract

Stochastic facility location problems with outsourcing costs (SFLPOC) optimize facility placement and customer assignment under demand uncertainty. Excess demand beyond a facility's capacity incurs outsourcing costs. This work addresses SFLPOC, aiming to minimize overall expected costs (installation, servicing, and outsourcing).

We model SFLPOC as a two-stage stochastic program. While prior work focused on specific assumptions or small scenario sets, we present methods suitable for general probability distributions. For discrete scenario sets, we improve upon classic Benders decomposition by exploiting the second-stage subproblem's structure.

To handle general distributions, we partition the probability space, enabling the computation of expected values with fewer scenarios. Coupled with Benders cuts, this provides an exact solution method for common distributions (e.g., Bernoulli, Gaussian).

Additionally, we introduce a compact formulation specifically for i.i.d. demand distributions, allowing us to solve even continuous distribution problems to optimality. Computational experiments on established benchmarks demonstrate that our compact formulation consistently finds optimal solutions, while the Benders approach provides strong solutions with proven optimality gaps for general distributions, outperforming sample average approximations.

Keywords

Status: accepted


Back to the list of papers