# Linear programming with a product term in the objective function

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

• To clarify, by binary variable you don't mean you are in $\mathbb{Z}_2$, but that you are identifying this with 0 and 1 (or something like that). Otherwise that minimum would be nonsense. – AHusain Jul 15 '16 at 23:36
• so the $B_i$ are fixed and the $x_i$ are the variables? – Jorge Fernández Hidalgo Jul 15 '16 at 23:41
• Sorry about the confusion. both of them are variables and $x_i$ is 0-1 variable – daydayup Jul 15 '16 at 23:57

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.