Using affine decision rules to solve a two-stage facility location problem with facility disruption

Problem Definition

We consider a facility location problem with facility disruption. Given a set of potential facility locations \(V_1\) and a set of customers \(V_2\), the goal is to select a subset of facility locations to activate in order to serve all customers’ demand, while minimizing the total cost. This version considers random disruptions of the opened facilities making them unusable.

Note that there is also an example for the deterministic version of the FLP using Column Generation.

Each facility \(i\in V_1\) has an opening cost \(f_i\) and a maximum capacity \(q_i\). Each customer \(j\in V_2\) has a demand \(d_j\). The unitary cost for serving customer \(j\in V_2\) from facility \(i\in V_1\) is \(t_{ij}\). The maximum number of facilities that can be disrupted is noted \(\Gamma\).

The two-stage robust facility location problem can be formulated as

\[\begin{align} \min_{ x\in \{0,1\}^{|V_1|} } \quad & \left\{ \sum_{i\in V_1} f_i x_i + \max_{\xi\in \Xi} \min_{y\in Y(x,\xi)} \quad \sum_{i\in V_1} \sum_{j\in V_2} t_{ij} y_{ij} \right\}, \end{align}\]

in which \(\Xi := \left\{ \xi\in\{0,1\}^{|V_1|} : e^\top\xi \le \Gamma \right\}\) and \(Y(x,\xi)\) is the feasible set of the second-stage problem defined as

\[\begin{split}\begin{align} & \sum_{j\in V_2} d_j y_{ij} \le q_i, && i\in V_1,\\ & \sum_{i\in V_1} y_{ij} \ge 1, && j\in V_2, \\ & y_{ij} \le x_i && i\in V_1, j\in V_2, \\ & y_{ij} \le 1 - \xi_i && i\in V_1, j\in V_2, \\ & x_i \in \{0,1\}, && i\in V_1, \\ & y_{ij} \in \{0,1\}, && i\in V_1, j\in V_2. \end{align}\end{split}\]

In this example, we will approximate the robust problem using affine decision rules and solve it using Gurobi. To this end, we will restrict the adjustable decisions to be affine functions of the uncertain parameters, i.e., \(y(\xi) = \bar y + Y\xi\).

Implementation