Solving a facility location problem with a custom branch-and-bound¶
Problem Definition¶
We consider the capacitated Facility Location Problem (FLP). 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 location to activate in order to serve all customers’ demand, while minimizing the total cost.
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}\).
We model the capacitated FLP with the MILP:
Instance¶
We will use an instance stored in a file called facility.data.txt. This file reads
On the first line, the number of facilities and the numbers of customers are specified. Then, for each facility, the opening cost and the capacity are given. For each customer, the demand is given. Finally, the cost of serving each customer from each facility is given.