In the following we describe the CIP model that we use: both the monolithic mixed integer program and the decomposed problem (using Benders' decomposition).

Given: a set of facilities \( I \) and a set of customers \( J \). The set of scenarios is given by \( S \), which are defined by a set of different customer demands.

Task: Find the minimum cost facilities to open such that the customer demand can be satisfied in all scenarios.

Variables:

• \( x_i \in \{0,1\} \quad \forall i \in I \):
  • \( x_i = 1 \) if facility \( i \) is opened.
• \( y^{s}_{ij} \ge 0 \quad \forall i \in I, \forall j \in J, \forall s \in S \)
  • \( y^{s}_{ij} \) is the level of demand for customer \( j \) satisfied by facility \( i \) in scenario \( s \).

Parameters:

• \( f_i \) the fixed cost for opening facility \( i \),
• \( q_{ij} \) the cost of servicing customer \( j \) from facility \( i \),
• \( \lambda^{s}_{j} \) the demand of customer \( j \) in scenario \( s \),
• \( k_i \) the capacity of facility \( i \).

The deterministic equivalent

The deterministic equivalent can be formulated as:

\[ \begin{array}[t]{rll} \min & \displaystyle \sum_{i \in I} f_{i} x_{i} + \frac{1}{|S|}\sum_{s \in S}\sum_{i \in I}\sum_{j \in J}q_{ij}y^{s}_{ij} \\ & \\ subject \ to & \displaystyle \sum_{i \in I} y^{s}_{ij} \ge \lambda^{s}_{j} & \quad \forall j \in J, \forall s \in S \\ & \\ & \displaystyle \sum_{j \in J} y^{s}_{ij} \le k_{i}x_{i} & \quad \forall i \in I, \forall s \in S \\ & \\ & \displaystyle \sum_{i \in I} k_{i}x_{i} \le \max_{s \in S}\sum_{j \in J}\lambda^{s}_{j} & \\ & \\ & \displaystyle x_{i} \in \{0, 1\} & \quad \forall i \in I \\ & \\ & \displaystyle y^{s}_{ij} \ge 0 & \quad \forall i \in I, \forall j \in J, \forall s \in S \\ \end{array} \]

It can be seen that as the number of scenarios increases, the size of the deterministic equivalent increases significantly. For large numbers of scenarios, the resulting deterministic equivalent can in intractable. This limitation can be addressed by applying decomposition techniques. In this example, Benders' decomposition is applied to solve the stochastic capacitated facility location problem.

Applying Benders' decomposition to the SCFLP

The application of Benders' decomposition forms a master problem, consisting of only the facility location variables, and a subproblem for each scenario, consisting of the customer servicing variables for the given secnario.

The master problem is given by:

\[ \begin{array}[t]{rll} \min & \displaystyle \sum_{i \in I} f_{i} x_{i} + \frac{1}{|S|}\sum_{s \in S}\varphi^{s} \\ & \\ subject \ to & \displaystyle \sum_{i \in I} k_{i}x_{i} \le \max_{s \in S}\sum_{j \in J}\lambda^{s}_{j} & \\ & \\ & \displaystyle \varphi^{s} \geq \sum_{j \in J}\lambda^{s}_{j}u^{p}_{j} + \sum_{i \in I}k_{i}x_{i}v^{p}_{i} & \quad \forall s \in S, \forall p \in P^{s} \\ & \\ & \displaystyle 0 \geq \sum_{j \in J}\lambda^{s}_{j}u^{r}_{j} + \sum_{i \in I}k_{i}x_{i}v^{r}_{i} & \quad \forall s \in S, \forall r \in R^{s} \\ & \\ & \displaystyle x_{i} \in \{0, 1\} & \quad \forall i \in I \\ & \\ & \displaystyle \varphi^{s} \geq 0 & \quad \forall s \in S \\ \end{array} \]

where \( \varphi^{s} \) is the auxiliary variable for each scenario \( s \) that is an underestimator of the optimal subproblem objective function value. The second and third constraint of the master problem are the Benders' optimality and feasibility cuts. Given a solution to the master problem, an optimality cut for scenario \(s\) is generated from the optimal dual solution to the corresponding subproblem. Similarly, if the solution to the master problem induces an infeasibl instance of subproblem \(s\), then the resulting dual ray is used to generate a feasibility cut.

The subproblem for scenario \( s \) that are solved to generate optimality and feasibility cuts are:

\[ \begin{array}[t]{rll} z^{s}(\bar{x}) = \min & \displaystyle \sum_{i \in I}\sum_{j \in J}q_{ij}y^{s}_{ij} \\ & \\ subject \ to & \displaystyle \sum_{i \in I} y^{s}_{ij} \ge \lambda^{s}_{j} & \quad \forall j \in J \\ & \\ & \displaystyle \sum_{j \in J} y^{s}_{ij} \le k_{i}\bar{x}_{i} & \quad \forall i \in I \\ & \\ & \displaystyle y^{s}_{ij} \ge 0 & \quad \forall i \in I, \forall j \in J \\ \end{array} \]

The solution \(\bar{x}\) is the candidate solution that is verified by solving the subproblem. As explained above, if the subproblem is infeasible, then the corresponding dual ray is used to generate a Benders' feasibility cut. If the subproblem is optimal and \( z^{s}(\bar{x}) > \varphi^{s} \), then an optimality cut is generated from the corresponding dual solution. If \( z^{s}(\bar{x}) \le \varphi^{s} \), then the subproblem is optimal for the given solution \( \bar{x} \). If \( z^{s}(\bar{x}) > \varphi^{s} \) for all scenario subproblems, then \( \bar{x} \) is the optimal solution to the original problem.