The title might sound a little weird. I actually want to ask if this problem can be solved as a LP. And if so, how to convert the product term?
set $P=\{1,2,3,\ldots,n\}$ for index $i$. Variables $B_i$ and $x_i$ are both indexed by $i$. $x_i$ is binary variable. All the constraints can be converted to linear constraints.
The objective is :
$\min \sum B_i x_i $, where $x_i$ is binary.
I know is the product term is in the constraints, then we can use the big-M coefficient to convert it to linear constraints. Is there a way to do this when the product term is in the objective function? Thank you.
PS: Both $B_i$ and $x_i$ are variables.There are many other decision variables and about 20 linear constraints. but other variables are not in the objective function so I didn't list them
Best Answer
To linearize the product $ B_ix_i $ in your objective function, replace it by $y_{i}$ and add the following constraints: \begin{cases} y_{i}\le Mx_{i}\\ y_{i}\le B_{i}\\ y_{i}\ge B_i-M(1-x_i) \\ y_{i}\ge 0 \end{cases} $M$ is a large constant. If $x_i=0$, it is easy to see that you will have $y_i=0$. And if $x_i=1$, you will have $y_i=B_i$.
Note: I assumed your variable $B_i$ is bounded below by $0$ already.