TITLE: Linearizing quadratic 0-1 function
QUESTION [0 upvotes]: I have the following as part of my objective function
z=$y_{wb} \sum_{w' \neq w} p(w') y_{w'b}$
s.t. $\sum_{w' \neq w} y_{w'b}=1$
where $y\in \{0,1\}$, and $p(w')$ is the probability of $w'$.
The function is not linear because of the multiplication between $y_{wb}$ and $y_{w'b}$. I did the following so far
As the summation over $w'$ is equal to one so only one probability will be counted. So taking the overage over the probabilities of all $w'$ (say $=A$) will give us the following
z is approximated by $y_{wb} \times A$ which is linear.
introducing a new variables like $K= y_{wb} \times y_{w'b}$ with the needed inequalities is not helpful as the number of variables in my problem is huge and this will increase so much.
Does any one recommend any other way to linearize $z$?

REPLY [1 votes]: Instead of the usual linearization of a product of binary variables, the equality constraints allow you to use compact linearization.  Introduce variables $x_{w,w',b}$ to represent the products $y_{w,b} y_{w',b}$.  Now you need these constraints:
\begin{align}
\sum_{w' \not= w} x_{w,w',b} &= y_{w,b} &&\text{for all $w,b$} \\
x_{w,w',b} &\le y_{w',b} &&\text{for all $w,w',b$ with $w \not= w'$}\\
x_{w,w',b} &\ge 0 &&\text{for all $w,w',b$ with $w \not= w'$}
\end{align}
If this is still too expensive, you could generate some of these constraints dynamically as cuts.
{"set_name": "stack_exchange", "score": 0, "question_id": 3420538}