Product of Polynomials of Binary Variables: Linearization

135 Views Asked by At

I have the following term (in the context of mathematical programming):

$$\prod_{p = 1}^P [1 - z_p(1 - \lambda_p)]$$

where $\lambda_p \in [0,1]$ is a parameter and $z_p \in \{0,1\}$ is a binary variable. I'd like to avoid having this nonlinear term in my formulation.

I'm aware of the following "trick" for products of binary variables: $\prod_{p = 1}^P z_p$ can be replaced by the following linear inequalities: $$w \leq z_p, \quad p = 1,\ldots,P$$ $$w \geq \sum_{p = 1}^P z_p - (P - 1)$$ where $w \in \{0,1\}$ is a newly introduced binary variable that replaces the product of $z_p$ variables.

The problem is that the original polynomial in $z_p$ is more complex than that. In my case, $P$ can be as large as 70 or even larger, so expanding the original product may not be practical. Any thoughts?

Thank you.