Capacitated Facility Location

The Capacitated Facility Location Problem (CFLP) considers satisfying customer demands from a set of candidate facilities. Each facility has a fixed opening cost and a capacity; once opened, it can serve customers, incurring a transportation cost that depends on the customer's demand and the distance between them. The goal is to decide which facilities to open and how to split every customer's demand among the open facilities so that the total opening and transportation cost is minimized. The instances follow the generator of [Gasse19], which in turn follows [Cornuéjols91].

Notation

• \(C\): the set of customers, indexed by \(i\); \(F\): the set of candidate facilities, indexed by \(j\).
• \(d_i\): demand of customer \(i\) (integer, uniform in \(\{5,\dots,35\}\)).
• \(s_j\): capacity of facility \(j\). Raw capacities are drawn uniformly from \(\{10,\dots,160\}\) and rescaled so that the total capacity is \(\rho = 5\) times the total demand (rounded down to integers).
• \(f_j\): fixed cost of opening facility \(j\), \(f_j = \lfloor u_j\sqrt{\tilde s_j} + v_j \rfloor\) with \(u_j\) uniform in \(\{100,\dots,110\}\), \(v_j\) uniform in \(\{0,\dots,90\}\), and \(\tilde s_j\) the raw (unscaled) capacity.
• \(c_{ij}\): cost of serving all of customer \(i\)'s demand from facility \(j\), \(c_{ij} = 10\, d_i\, \lVert p_i - q_j \rVert_2\), where customer locations \(p_i\) and facility locations \(q_j\) are uniform in the unit square.
• \(y_j \in \{0,1\}\): 1 if facility \(j\) is opened.
• \(x_{ij} \in [0,1]\): fraction of customer \(i\)'s demand served by facility \(j\).

MILP formulation

\begin{align} \min_{x,y} \quad & \sum_{i \in C}\sum_{j \in F} c_{ij}\, x_{ij} + \sum_{j \in F} f_j\, y_j \\ \text{s.t.} \quad & \sum_{j \in F} x_{ij} \geq 1 && \forall i \in C \quad \text{(demand)} \\ & \sum_{i \in C} d_i\, x_{ij} \leq s_j\, y_j && \forall j \in F \quad \text{(capacity)} \\ & \sum_{j \in F} s_j\, y_j \geq \sum_{i \in C} d_i && \text{(total capacity)} \\ & x_{ij} \leq y_j && \forall i \in C,\ \forall j \in F \quad \text{(only open facilities serve)} \\ & 0 \leq x_{ij} \leq 1 && \forall i \in C,\ \forall j \in F \\ & y_j \in \{0,1\} && \forall j \in F \end{align}

The total-capacity constraint and the \(x_{ij} \leq y_j\) constraints are implied by the others for integer \(y\), but they are included in the instances to tighten the LP relaxation [Gasse19]. An instance therefore has \(|F|\) binary variables, \(|C||F|\) continuous variables, and \(|C| + |F| + 1 + |C||F|\) constraints.

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

@article{cornuejols1991comparison,
  title={A comparison of heuristics and relaxations for the capacitated plant location problem},
  author={Cornu{\'e}jols, G{\'e}rard and Sridharan, Ranjani and Thizy, Jean-Michel},
  journal={European journal of operational research},
  volume={50},
  number={3},
  pages={280--297},
  year={1991},
  publisher={Elsevier}
}