Solving a robust facility location problem by its deterministic equivalent¶
Problem Definition¶
We consider a facility location problem with uncertain demand. 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 introduces uncertainty in the customers’ demands.
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 uncertainty in customer demands is controlled by a parameter \(\Gamma\).
In this robust variant, we consider that the demands are uncertain and can be expressed as \(d_j(\xi) = d_j(1 + 0.2 \xi_j)\) with \(\xi\) being an unknown vector taken in the uncertainty set
The goal is to minimize the total cost of opening facilities and serving customers, considering the worst-case demand scenario.
The robust version can be formulated as
In this example, we will reformulate this robust facility location problem as a deterministic one. Then, we will solve it using Gurobi.
Hint
Here, the deterministic reformulation reads as follows.