Linearize function

Question

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?

Answer 1

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.