Is this linearisation of the uncapacitated facility location problem correct?

79 Views Asked by At

Assume we have $n$ factories with unlimited capacity that produce a certain product. The costs to build the factories are $c_1, \ldots, c_n$ respectively. There are $m$ clients whose demands for this product are $d_1, \ldots, d_m$ units respectively. We also have $e_{ij}$ is the cost to deliver $1$ unit from factory $i$ to client $j$. The total cost is the sum of building cost and delivery cost. Determine which factories should we build to minimize the total cost.

This is known as uncapacitated facility location problem. Could you please verify if my linearisation of the product $x_i y_{ij}$ of a binary variable $x_i$ and a continuous $y_i$ is correct?


Let $x_i = 1$ if the factory $i$ is built and $0$ otherwise. Let $y_{ij}$ be the proportion of $d_j$ supplied by factory $i$. To simplify notation, let $[m] := \{1, \ldots m\}$ and $[n] := \{1, \ldots n\}$. Then our problem becomes

$$ \begin{aligned} \text{min} & \quad \sum_{i=1}^n c_i x_i + \sum_{j=1}^m \sum_{i=1}^n d_j e_{ij} x_i y_{ij}\\ \text{s.t} & \quad x_i \in \{0, 1\} && \text{for all} \quad i \in [n] \\ & \quad y_{ij} \in [0, 1] && \text{for all} \quad (i, j) \in [n] \times [m] \\ & \quad \sum_{i=1}^n x_i y_{ij}= 1 && \text{for all} \quad j \in [m] \end{aligned} $$

Then I want to linearise this optimisation problem as follows. Let $z_{ij} := x_i y_{ij}$. Then our problem becomes

$$ \begin{aligned} \text{min} & \quad \sum_{i=1}^n c_i x_i + \sum_{j=1}^m \sum_{i=1}^n d_j e_{ij} z_{ij}\\ \text{s.t} & \quad x_i \in \{0, 1\} && \text{for all} \quad i \in [n] \\ & \quad z_{ij} \in [0, 1] && \text{for all} \quad (i, j) \in [n] \times [m] \\ & \quad \sum_{i=1}^n z_{ij}= 1 && \text{for all} \quad j \in [m] \end{aligned} $$

1

There are 1 best solutions below

0
On BEST ANSWER

Close, but not quite.

To see that your reformulation is not correct, note that if we have $c_i > 0$ for all $i$, then any optimal solution of your reformulated version will have $x_i=0$ for all $i$, hence the minimum possible value for your reformulated version will be less than the minimum possible value for the original version.

As a way to fix it, you can include the constraints $z_{ij}\le x_i$ for all $i,j$ in order to guarantee $z_{ij}=0$ whenever $x_i=0$.

But note: Since the variables $x_i$ are binary, you have a mixed-integer linear program, not a linear program.