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?

  • $\begingroup$ 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\}$ $\endgroup$ – callculus Nov 19 '18 at 22:49
  • $\begingroup$ @callculus : I believe this is wrong. Nothing forces variables $Y_j$ to take value $1$ when $X_{ij}=1$. $\endgroup$ – Kuifje Nov 21 '18 at 12:33

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 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.