2
$\begingroup$

I have a facility location problem with a non-linear objective;

  • There are fixed costs $S_j$ to opening facility $j$
  • $Y_j$ is a binary, $1$ if facility $j$ is opened, $0$ otherwise
  • $D_j$ is the number of products that will be gathered at facility $j$
  • It is cheaper to assign more products to an open facility as fixed costs can be spread. Therefore, there is a negative slope of $-a\cdot D_j$ when a facility is open. Indicating that when more products are assigned to an open collection point, this will be deducted from the fixed cost.

This gives the objective function $$S_j \cdot Y_j - a \cdot D_j \cdot Y_j$$

How do I linearize this to create a linear programming problem?

$\endgroup$

1 Answer 1

5
$\begingroup$

One approach is to perform the usual linearization of a product of a bounded variable and a binary variable, by introducing a new variable to represent the product, along with additional linear constraints to enforce the desired relationships. A simpler approach is to replace $S_j Y_j - a D_j Y_j$ with $S_j Y_j - a D_j$ and enforce the logical implication $D_j > 0 \implies Y_j = 1$. Equivalently, you can enforce the contrapositive $$Y_j = 0 \implies D_j = 0$$ either directly as an indicator constraint or indirectly via linear big-M constraint $$D_j \le M_j Y_j,$$ where $M_j$ is a (small) upper bound on $D_j$ when $Y_j = 1$. For example, you can take $M_j$ to be the total number of products.

$\endgroup$
5
  • $\begingroup$ Thank you for you answer! However, I think there is still an issue, due to something I haven't explained yet. Facilities have internal supply; w_j. Therefore D_j = w_j + X_ij, where X_ij is a binary variable, 1 if customer i is assigned to facility j, 0 otherwise. Therefore, D_j is always >0, as each facility has w_j. With the latter method you explained, this would always lead to Y_j=1 $\endgroup$
    – user9867
    Jun 22 at 12:54
  • $\begingroup$ @user9867 Your problem statement says that $D_j$ is "the number of products that will be gathered at facility $j$". So now you are saying that a positive amount will be gathered at facility $j$ ($D_j >0$ even if facility $j$ is closed ($Y_j=0$)? $\endgroup$
    – prubin
    Jun 22 at 15:16
  • $\begingroup$ @user9867 Do you maybe mean instead that $D_j = w_j + \sum_i X_{ij}$? $\endgroup$
    – RobPratt
    Jun 22 at 18:00
  • $\begingroup$ @RobPratt yes that is what I mean! It is possible to have products at a facility without opening a collection point, therefore D_j will always be positive $\endgroup$
    – user9867
    Jun 23 at 6:47
  • $\begingroup$ Then I suggest replacing $D_j$ with $D_j-w_j$ in the constraints. $\endgroup$
    – RobPratt
    Jun 23 at 12:18

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.