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?
$\endgroup$ 21 Answer
$\begingroup$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 $$
$\endgroup$
