3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – AHusain Jul 15 '16 at 23:36
  • 1
    $\begingroup$ so the $B_i$ are fixed and the $x_i$ are the variables? $\endgroup$ – Jorge Fernández Hidalgo Jul 15 '16 at 23:41
  • $\begingroup$ Sorry about the confusion. both of them are variables and $x_i$ is 0-1 variable $\endgroup$ – daydayup Jul 15 '16 at 23:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's amazing!! How do you compose this @Kuifje ? Is there a compilation somewhere of all these tricks in linear programming? Thank you very much. $\endgroup$ – daydayup Jul 16 '16 at 1:15
  • 1
    $\begingroup$ I personally learned a lot through my different courses via many different references. But to be honest, type "linearize product" on google and the first link will give you the trick I wrote :) $\endgroup$ – Kuifje Jul 16 '16 at 1:29

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.