2
$\begingroup$

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

1 Answer 1

Reset to default
2
$\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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.