# Facility Location Problem with Integer Linear Programming

I am trying to create a linear programming formulation based on a facility location problem. In this problem, it is the goal to minimize the costs of travelling from 50 customers to 3 facilities. These have yet to be built and there are 20 possible locations for these facilities.

When setting the objective function and the constraints, it is a challenge to link the maximum of 3 facilities with links between customer and facility in the constraints. Let me explain a bit more mathematically. Please assume that demand and capacity is not an issue and that each route is driven once per time unit.

Between customer i and facility j, there is a possible link Xij. When Xij is 1, it means that a connection is established, and 0 if not. There can be 3 facilities Yj opened. The cost function Cij of opening a link is used in the objective function.

The objective function $$MIN \quad \sum_{i=1}^{50}\sum_{j=1}^{20}C_{ij} X_{ij}$$ defines the goal of minimizing costs.

This is constrained by: $$\sum_{j=1}^{20} Y_j \le 3 \quad \mbox{(there may be 3 facilities opened)}$$

Now my issue is, how can this Yj be related to the Xij, meaning that there cannot be a link opened between a customer and non-existing facility?

I was thinking something with: $$\sum_{i=1}^{50} X_{ij} \ge Y_j$$ There cannot be a link between a facility if that one is not opened, but the number of links with a specific facility is unlimited

Is my way of thinking correct and would it work, or is there something wrong with my way of thinking?

• It is right. The constraint is $$\sum_{i=1}^{50}X_{ij} \geq Y_j \ \ \ \forall \ \ j=1,2,3$$ $X_{ij}, Y_j\in \{0,1\}$ – callculus Nov 19 '18 at 22:49
• @callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$. – Kuifje Nov 21 '18 at 12:33

## 1 Answer

Each customer should be assigned to exactly one facility : $$\sum_{j=1}^{20} X_{ij}=1 \quad \forall i=1,...,50$$ and if customer $$i$$ is assigned to facility $$j$$, it means that facility $$j$$ is opened : $$X_{ij} \le Y_j\quad \forall i=1,...,50 \quad \forall j =1,...,20$$